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

[king8313 ()]

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
推 TMDTMD2487: 要阿 你畫個遞迴樹 把東西加一加看看
推 TMDTMD2487: 前n-1層的數量跟第n層的樹葉數是一樣的等級
→ TMDTMD2487: 就畫個滿滿的樹應該能輕易看的出來
→ TMDTMD2487: 然後樹葉之前的都是O(1) 樹葉則是O(M)
→ TMDTMD2487: 不要太嚴謹的話這樣想一下比較容易
→ TMDTMD2487: 如果有L個樹葉那內部節點有L-1個(滿的樹
→ TMDTMD2487: 內部節點都是O(1) 而樹葉是O(M) 就只是這樣而已@@
推 TMDTMD2487: 豁然想到我討論的是二元樹不過這個遞迴是degree 8的
→ TMDTMD2487: 不過我相信沒有差就是了
→ TMDTMD2487: degree越大前n-1層的數量和跟第n層的只會差更大
→ king8313: 感謝T大的詳細解說!!
→ king8313: 大概了解了!