递推关系的运行时

Question

刚把此上测验：T（N）= 4T（SQRT（n））的+ 5

我简化它使用替换，并得到F（k）的= 4F（K/2） + 5

使用主定理我猜想它是O（logn）。这是否准确？

Answer 1

定义

F(n) = T(2^n) 

然后我们有

F(n) = 4F(n/2) + 5 

由主定理，我们有

a = 4 
b = 2 
f(n) = 5 = O(1) = O(m^0), so c = 0 
0 < 2 = log_2(4) 

因此，我们在主定理的情况下，1。通过案例1，我们有

F(n) = Theta(n^2) 

所以

T(2^n) = Theta(n^2) 

因此

T(n) = Theta(log(n^2)) = Theta(2logn) = Theta(log n) 

所以，是的，你的答案似乎是正确的。