在王志强资料结构[递回]那章节
P5-59 40题的(5)小题，求复杂度Θ
T(n) = 2T(√n) + log(n)
我的解法:
令n=(2的2的k次方) => k=log(log(n))这之后会用到
T(2的2的k次方)=2T(2的2的k-1次方)+2的k次方
令Ak=T(2的2的k次方)
PS:Ak写法是..k在A的右小脚
得到递回关系式
A(k)-2A(k-1)=2的k次方
PS:括号内皆在A的右下角
改成齐次式
A(k)-3A(k-1)+2A(k-2)=0
PS:括号内皆在A的右下角
所以特征方程式:
r的平方-3r+2=0
r=2 or 1
Ak=C1*2的k次方 + C2
因k=log(log(n))
Ak=C1*2的log(log(n))次方 + C2
=C1*log(n)的log(2)次方 + C2
=C1*log(n) + C2
=>Θ(log(n))
但解答不是log(n)，是...
log(n)*log(log(n))
请问是我哪里算错或是答案有问题呢?
感谢!!!