algorithm - 使用主定理的算法成本

Question

你好，谁能帮我解决这个问题

T(n)=T(n^(1/2)) + theta (lg lg n)

这就是我到目前为止所做的让

m = lg n
s(m)=s(m/2) + theta (lg m)

在这里应用主定理

a=1 b=2
m^log 2 (1) = m^0 =1 

现在卡住了。

Answer 1

你有：

a = 1, b = 2
f(m) = Ө(lg(m))

主定理的第二种情况适用于：

f(m) = Ө(m^c * lg^k(m))

在哪里：

c = log_b(a)

对此进行测试，我们有：

f(m) = Ө(lg(m)) = Ө(m^0 * lg(m)) 
-> c = 0
-> c = log_b(a) = log_2(1) = 0

所以第二种情况确实适用。因此，递归的解决方案是：

T(m) = Ө(m^c * lg²(m)) = Ө(lg²(m))

代入m，我们回到

T(n) = Ө(lg²(lg(n)))

Answer 2

首先，T(n) = T(n^(1/2)) + theta(lg lg n) 可以写成

T(2^(2^k)) = T(2^(2^(k-1))) + theta(k)。

将 k=1 的上述方程聚合到 d 得到 T(2^(2^d)) = theta(d^2)。令 n=2^(2^d)，我们得到 T(n) = theta( (lg lg n)^2 )。