求緊密界線Θ - 考試

在王志強資料結構[遞迴]那章節

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))



請問是我哪裡算錯或是答案有問題呢?
感謝!!!

--
This is SPARTA!
我只是要土和水
拿來種種花啊!!! \固
囧//☆︿異╲
█ ☆ \ by aokman
████████◤ \\ ◥██aokman███████████████

--