<分区>
谁能帮我解决这个问题？
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
现在我卡住了。
<分区>
谁能帮我解决这个问题？
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
现在我卡住了。
最佳答案
你有:
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)))
关于使用主定理的算法成本，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28905213/