[理工] 105台大資結 時間複雜度

看板Grad-ProbAsk作者時間8年前 (2017/12/09 18:43), 編輯推噓3(3推 0噓 9→)
留言12則, 2人參與, 8年前最新討論串1/1
https://i.imgur.com/bKHQI7V.jpg
請問一下這一題 為什麼Total cost is dominated by leaves? 那內部節點的overhead不用一起考慮嗎 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 120.126.194.203 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1512816181.A.A29.html
推
12/09 20:20, 8年前 , 1F
要阿 你畫個遞迴樹 把東西加一加看看
12/09 20:20, 1F
推
12/09 20:31, 8年前 , 2F
前n-1層的數量跟第n層的樹葉數是一樣的等級
12/09 20:31, 2F
→
12/09 20:31, 8年前 , 3F
就畫個滿滿的樹應該能輕易看的出來
12/09 20:31, 3F
→
12/09 20:32, 8年前 , 4F
然後樹葉之前的都是O(1) 樹葉則是O(M)
12/09 20:32, 4F
→
12/09 20:33, 8年前 , 5F
不要太嚴謹的話這樣想一下比較容易
12/09 20:33, 5F
→
12/09 20:34, 8年前 , 6F
如果有L個樹葉那內部節點有L-1個(滿的樹
12/09 20:34, 6F
→
12/09 20:34, 8年前 , 7F
內部節點都是O(1) 而樹葉是O(M) 就只是這樣而已@@
12/09 20:34, 7F
推
12/09 20:37, 8年前 , 8F
豁然想到我討論的是二元樹不過這個遞迴是degree 8的
12/09 20:37, 8F
→
12/09 20:37, 8年前 , 9F
不過我相信沒有差就是了
12/09 20:37, 9F
→
12/09 20:38, 8年前 , 10F
degree越大前n-1層的數量和跟第n層的只會差更大
12/09 20:38, 10F
→
12/09 21:58, 8年前 , 11F
感謝T大的詳細解說!!
12/09 21:58, 11F
→
12/09 21:59, 8年前 , 12F
大概了解了!
12/09 21:59, 12F
‣ 更多 king8313 的文章
文章代碼(AID): #1QAxuref (Grad-ProbAsk)