106 台聯大 離散 遞迴

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