作者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/cn.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