作者k1006boy (@@)
看板Prob_Solve
標題[問題] heapify worst case
時間Mon Oct 5 12:35:35 2009
我看Introduction to algorithms
在分析MAX-heapify T(n) = T(2n/3) + O(1)
有一句話是這樣說的
the children's subtrees each have size at most 2n/3
the worst case occurs when the last level of the tree is exactly half full
我是想問 2n/3是如何求得的?
那本書那一段話怎麼看我都看不懂@@
謝謝了..
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.123.104.24
※ 編輯: k1006boy 來自: 140.123.104.24 (10/05 12:45)
※ 編輯: k1006boy 來自: 140.123.104.24 (10/05 12:47)
※ 編輯: k1006boy 來自: 140.123.104.24 (10/05 12:47)
1F：→ k1006boy:沒記錯是在p.131 10/05 12:48
2F：推 raincole:兩個子樹為高度差1的全滿二元樹，則高的有2x個節點 10/05 19:45
3F：→ raincole:低的有x個 故高子樹節點數為整體節點數的2/3（2x/3x） 10/05 19:46
4F：→ raincole:我描述能力有點差 你畫一個有9個節點的binary heap 10/05 19:49
5F：→ raincole:就會知道書中那段的意思了 10/05 19:49