遞推關係的運行時

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) 

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