如何用主定理求解这个递推方程T（n）=√2T（n/2）+ log n？

Question

我知道它可以用主方法解决，但怎么样？请帮忙 ？

Answer 1

我不知道这是否是正确的：

a = sqrt(2) 
b = 2 
f(n) = log n 
log(b) a = log (2) sqrt(2) = 1/2 

log n in O[n^(1/2)] 

所以寻找一个数的对数n的运行时间为O {N ^（1/2）}（但是法师定理不能应用在这里）

的解决方案是在以下主题：Solving master theorem with log n: T(n) = 2T(n/4) + log n

总体上，我们看到你的复发是O（N1/2）和Ω（N1/2）的上限和下限的边界重复发生越来越小的复发。因此，即使主定理不适用于此，仍然可以使用主定理来声明运行时将为Θ（n1/2）。

Master's theorem with f(n)=log n

通常情况下，F（N）必须是多项式的主定理应用 - 它并不适用于所有的功能。但是，对于主定理，有一个有限的“第四种情况”，它允许它适用于多对数函数。

https://en.wikipedia.org/wiki/Master_theorem

https://en.wikipedia.org/wiki/Big_O_notation

Answer 2

拉尔夫是不是告诉你正确的，你不能apply masters theorem。

这里唯一的限制是a >=1和b >= 1，a，b可以是非理性的，f（n）可以是任何东西。

Log2(sqrt(2)) is 1/2，这会使您处于第一种情况，您的解决方案是O(n^0.5)。