→ kopk159: 假設 n>=3，T(n) <= 2T(n/8 + n/8) +n，master theory 01/22 23:34
→ kopk159: 取得upper bound 01/22 23:34
→ kopk159: T(n) >= 2T(n/8) + n ，取得lower bound 01/22 23:34
→ mathtsai: 原來能這樣解 謝謝樓上 01/23 00:08
→ x3767x: 感謝k大！原來還能這樣解 01/23 00:13
→ mathtsai: 想請問第二題怎麼解？ Substitution Method？ 01/23 00:25
推 shashayou: 求問第二題+1 01/23 02:49
→ nctujumpegg: 第二題是recursive tree 嗎？ 01/23 04:42
→ mathtsai: 猜他 < cn-b 然後用substitution method證明吧 01/23 06:04
推 alex391a: 第二題畫樹就好了吧 01/23 12:58
→ x3767x: 沒錯第二題畫Recursive tree就可以解了 01/23 13:09
→ mathtsai: 想請問畫出來答案是多少？ 01/23 14:01
→ mathtsai: 我是算O(n) 01/23 14:53
→ x3767x: 回樓上我是寫這樣 01/23 15:03
→ mathtsai: 感謝 不錯第二行為什麼不是 n/20 和 n/4 ？ 01/23 15:17
→ mathtsai: *不過* 01/23 15:17
→ mathtsai: 是我看錯題目嗎QQ 01/23 15:18
→ x3767x: 4 01/23 15:27
推 alex391a: 其實是7/20 跟1/4啦 不過答案一樣 01/23 16:22
→ alex391a: 只要總共小於一基本上都會是n 01/23 16:22
→ alex391a: 更正應該說如果後面的f(n)=n的話 01/23 16:23
→ mathtsai: 我也是畫7/20跟1/4 01/23 18:47