algorithm - 递归关系的运行时间

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)

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