在王志強資料結構[遞迴]那章節
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))
請問是我哪裡算錯或是答案有問題呢?
感謝!!!