[理工] [資結] 遞迴式

[boy5548 (小YO)]

有題遞回式 T(n)=T(n-2)+2lgn

我解法如下     =T(n-4)+2(lg(n-2)+lgn)
               =T(n-6)+2(lg(n-4)+lg(n-2)+lgn)
               =T(n-8)+2(lg(n-6)+lg(n-4)+lg(n-2)+lgn)
               =...
               =T(n-n)+2(1+2+...+lgn)
               =T(0)+2(lgn(lgn+1)/2)
               =T(0)+lgnlgn+lgn

               Time:Θ(lgnlgn)

因為手邊沒解答 請各位檢查一下正確性 謝謝:)

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.39.6.117
推 weiyung:最後應該不會是1+2+3+...+logn哩
→ weiyung:應該是log2+log4+log6+log8+....+logn
→ weiyung:我最後算出來是T(0)+n+2log(n/2)!
→ weiyung:大約是O(nlogn) 不知道對不對@@
推 death888:請問log2+log4+log6+log8+....+logn=log(2*4*...*n)
→ death888:再來要怎麼化簡呢
推 weiyung:變成log2^(n/2)*(1*2*3*...*n/2)
→ weiyung:這樣就等於log2^(n/2)*(n/2)!
→ boy5548:我好像錯了 因為之前寫是寫nlgn 所以想確認一下
※ 編輯: boy5548         來自: 114.39.6.117         (02/10 11:37)
推 qk211:log2+log4+..+logn=log(2*4*6*..*n)=log2*(1*2*..*n/2)=
→ qk211:log2+log((n/2)!)=log2+(n/2)log(n/2)=O(nlogn)