[理工] 演算法 recurrence 的問題

看板Grad-ProbAsk作者 (尼歐)時間12年前 (2014/02/04 15:16), 編輯推噓3(3推 0噓 20→)
留言23則, 4人參與, 最新討論串1/1
題目： 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)
→
02/04 16:17, , 1F
那個sub什麼的其實就是數學歸納法…
02/04 16:17, 1F
→
02/04 17:29, , 2F
恩 但是我歸納不出來 因為有地板函數 不知道要怎麼假設
02/04 17:29, 2F
→
02/04 17:30, , 3F
想說有沒有人可以寫一下完整的推導過程給小弟參考:)
02/04 17:30, 3F
推
02/04 17:48, , 4F
地板函數基本上不太影響吧
02/04 17:48, 4F
→
02/04 18:08, , 5F
如果要用induction 的話 地板函數是有影響的喲
02/04 18:08, 5F
推
02/04 18:34, , 6F
這題很難，一開始看好像基本題，剛想了一下，參考看看。
02/04 18:34, 6F
→
02/04 18:36, , 7F
02/04 18:36, 7F
→
02/04 19:50, , 8F
感謝A大! 但小弟還是有問題, 最後面好像沒有導出完整型式
02/04 19:50, 8F
→
02/04 19:53, , 9F
A最後導出 c(n-b)log(n-2b-2) 好像應該進一步處理log項
02/04 19:53, 9F
→
02/04 19:55, , 10F
先把它"喬"成 c(n-b)log(n-b) 然後再往下推導的樣子?
02/04 19:55, 10F
→
02/04 20:06, , 11F
前面都被吃掉了，log理面差一點點順手吃了，應該還可以。
02/04 20:06, 11F
→
02/04 20:08, , 12F
如果1<=b<=2 則(n-2b-2)<(n-b) 這樣是不是就有點怪?
02/04 20:08, 12F
→
02/04 20:10, , 13F
恩 我是想說歸納法好像要嚴謹一點
02/04 20:10, 13F
→
02/04 20:12, , 14F
關鍵是(-b-2)log < (1-c)n 因為 c 在01之間，n是正的。
02/04 20:12, 14F
→
02/04 20:14, , 15F
恩我懂 不過這樣就跟忽略地板函數來證明 一樣?
02/04 20:14, 15F
→
02/04 20:56, , 16F
02/04 20:56, 16F
→
02/04 20:56, , 17F
本來以為輕鬆吃，要證明也不容易...
02/04 20:56, 17F
→
02/04 21:38, , 18F
感謝A大相助，小弟懂了。基本上要能湊出b,c,n的範圍
02/04 21:38, 18F
→
02/04 21:38, , 19F
感覺考試的時候，直接送他比較快@@
02/04 21:38, 19F
→
02/04 21:43, , 20F
A大你後來寫的答案 好像要考慮c(2b-2)這項?
02/04 21:43, 20F
→
02/04 22:07, , 21F
那就是一個常數而已，n大一點就忽略了。
02/04 22:07, 21F
推
02/04 23:26, , 22F
02/04 23:26, 22F
→
02/05 18:36, , 23F
正解! 不愧是rnbjacky大!
02/05 18:36, 23F
‣ 更多 leosnake 的文章
文章代碼(AID): #1Iy9FSgv (Grad-ProbAsk)