106 台联大离散递回 x3767x PTT批踢踢实业坊

楼主: x3767x (x3767x) 2021-01-22 22:34:32

https://i.imgur.com/XN8ZnnY.jpg
想请问这题的a要怎么解
请各位指教了

作者: kopk159 (ChingYu) 2021-01-22 23:34:00

假设 n>=3，T(n) <= 2T(n/8 + n/8) +n，master theory取得upper boundT(n) >= 2T(n/8) + n ，取得lower bound

作者: mathtsai (mathtsai) 2021-01-23 00:08:00

原来能这样解谢谢楼上

楼主: x3767x (x3767x) 2021-01-23 00:13:00

感谢k大！原来还能这样解

作者: mathtsai (mathtsai) 2021-01-23 00:25:00

想请问第二题怎么解？ Substitution Method？

作者: shashayou (吓吓你) 2021-01-23 02:49:00

求问第二题+1

作者: nctujumpegg (交大超猛小跳蛋) 2021-01-23 04:42:00

第二题是recursive tree 吗？

作者: mathtsai (mathtsai) 2021-01-23 06:04:00

猜他 < cn-b 然后用substitution method证明吧

作者: alex391a (麦基) 2021-01-23 12:58:00

第二题画树就好了吧

楼主: x3767x (x3767x) 2021-01-23 13:09:00

没错第二题画Recursive tree就可以解了

作者: mathtsai (mathtsai) 2021-01-23 14:01:00

想请问画出来答案是多少？我是算O(n)

楼主: x3767x (x3767x) 2021-01-23 15:03:00

作者: mathtsai (mathtsai) 2021-01-23 15:17:00

感谢不错第二行为什么不是 n/20 和 n/4 ？*不过*是我看错题目吗QQ

楼主: x3767x (x3767x) 2021-01-23 15:27:00

作者: alex391a (麦基) 2021-01-23 16:22:00

其实是7/20 跟1/4啦不过答案一样只要总共小于一基本上都会是n更正应该说如果后面的f(n)=n的话

作者: mathtsai (mathtsai) 2021-01-23 18:47:00

我也是画7/20跟1/4

继续阅读