[理工] 演算法 recurrence 的問題

[leosnake (尼歐)]

題目：

Show that the solution of T(n) = 2T(floor(n/2)) + n is Ω(nlgn)

(抱歉 不會輸入地板的符號^^")

請教各位大大要如何用substitution method 證明呢?

感謝囉:)

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.47.196
※ 編輯: leosnake        來自: 61.230.47.196        (02/04 15:17)
→ A4P8T6X9:那個sub什麼的其實就是數學歸納法…
→ leosnake:恩 但是我歸納不出來 因為有地板函數 不知道要怎麼假設
→ leosnake:想說有沒有人可以寫一下完整的推導過程給小弟參考:)
推 lexwu200212:地板函數基本上不太影響吧
→ leosnake:如果要用induction 的話 地板函數是有影響的喲
推 A4P8T6X9:這題很難，一開始看好像基本題，剛想了一下，參考看看。
→ A4P8T6X9:http://ppt.cc/7KZ3
→ leosnake:感謝A大! 但小弟還是有問題, 最後面好像沒有導出完整型式
→ leosnake:A最後導出 c(n-b)log(n-2b-2) 好像應該進一步處理log項
→ leosnake:先把它"喬"成 c(n-b)log(n-b) 然後再往下推導的樣子?
→ A4P8T6X9:前面都被吃掉了，log理面差一點點順手吃了，應該還可以。
→ leosnake:如果1<=b<=2 則(n-2b-2)<(n-b) 這樣是不是就有點怪?
→ leosnake:恩 我是想說歸納法好像要嚴謹一點
→ A4P8T6X9:關鍵是(-b-2)log < (1-c)n 因為 c 在01之間，n是正的。
→ leosnake:恩我懂 不過這樣就跟忽略地板函數來證明 一樣?
→ A4P8T6X9:http://ppt.cc/sD7~
→ A4P8T6X9:本來以為輕鬆吃，要證明也不容易...
→ leosnake:感謝A大相助，小弟懂了。基本上要能湊出b,c,n的範圍
→ leosnake:感覺考試的時候，直接送他比較快@@
→ leosnake:A大你後來寫的答案 好像要考慮c(2b-2)這項?
→ A4P8T6X9:那就是一個常數而已，n大一點就忽略了。
推 rnbjacky:http://tinyurl.com/k867pse  參考看看
→ leosnake:正解! 不愧是rnbjacky大!