[課業] 資料結構求緊密界線Θ

看板Examination (國家考試)作者motai (啥暱稱??)時間12年前 (2014/07/18 13:36)推噓0(0推 0噓 7→)

留言7則, 3人參與討論串1/1

在王志強資料結構[遞迴]那章節 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███████████████ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.25.130.92 ※ 文章網址: http://www.ptt.cc/bbs/Examination/M.1405661781.A.136.html

→

panda555

07/18 13:58, , 1^F

07/18 13:58, 1^F

→

malowda

07/18 13:59, , 2^F

07/18 13:59, 2^F

→

malowda

07/18 14:01, , 3^F

07/18 14:01, 3^F

感謝提醒不好意思是我打錯了，從計算紙抄過來時打錯的請問接下來哪裡算錯呢? ※ 編輯: motai (114.25.130.92), 07/18/2014 14:32:50

[課業] 資料結構 求緊密界線Θ

[課業] 資料結構求緊密界線Θ