https://i.imgur.com/bKHQI7V.jpg
請問一下這一題
為什麼Total cost is dominated by leaves?
那內部節點的overhead不用一起考慮嗎

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

感謝T大的詳細解說!!大概了解了!