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

繼續閱讀