作者x3767x (x3767x)
看板Grad-ProbAsk
標題106 台聯大 離散 遞迴
時間Fri Jan 22 22:34:32 2021
https://i.imgur.com/XN8ZnnY.jpg
想請問這題的a要怎麼解
請各位指教了
-----
Sent from JPTT on my iPad
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.219.152.207 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1611326074.A.037.html
1F：→ kopk159: 假設 n>=3，T(n) <= 2T(n/8 + n/8) +n，master theory 01/22 23:34
2F：→ kopk159: 取得upper bound 01/22 23:34
3F：→ kopk159: T(n) >= 2T(n/8) + n ，取得lower bound 01/22 23:34
4F：→ mathtsai: 原來能這樣解 謝謝樓上 01/23 00:08
5F：→ x3767x: 感謝k大！原來還能這樣解 01/23 00:13
6F：→ mathtsai: 想請問第二題怎麼解？ Substitution Method？ 01/23 00:25
7F：推 shashayou: 求問第二題+1 01/23 02:49
8F：→ nctujumpegg: 第二題是recursive tree 嗎？ 01/23 04:42
9F：→ mathtsai: 猜他 < cn-b 然後用substitution method證明吧 01/23 06:04
10F：推 alex391a: 第二題畫樹就好了吧 01/23 12:58
11F：→ x3767x: 沒錯第二題畫Recursive tree就可以解了 01/23 13:09
12F：→ mathtsai: 想請問畫出來答案是多少？ 01/23 14:01
13F：→ mathtsai: 我是算O(n) 01/23 14:53
14F：→ x3767x: 回樓上我是寫這樣 01/23 15:03
16F：→ mathtsai: 感謝 不錯第二行為什麼不是 n/20 和 n/4 ？ 01/23 15:17
17F：→ mathtsai: *不過* 01/23 15:17
18F：→ mathtsai: 是我看錯題目嗎QQ 01/23 15:18
19F：→ x3767x: 4 01/23 15:27
20F：推 alex391a: 其實是7/20 跟1/4啦 不過答案一樣 01/23 16:22
21F：→ alex391a: 只要總共小於一基本上都會是n 01/23 16:22
22F：→ alex391a: 更正應該說如果後面的f(n)=n的話 01/23 16:23
23F：→ mathtsai: 我也是畫7/20跟1/4 01/23 18:47