每當我們洗掉一個根元素時，二叉樹的高度就會不斷降低。為什么我們使用n（元素總數）乘以logn（每次洗掉根元素時的交換量）來計算總時間復雜度，而交換量實際上取決于剩余元素的數量？
似乎時間復雜度的正確表達應該是根元素洗掉的每次迭代發生的交換總和。掉期金額為log(i). i是剩余的元素，log(i)是二叉樹的深度/時間復雜度/移除每個元素的交換量。i范圍從1到n。log(1)從到的總和log(n)只是O(log(n!))，它小于預期的復雜性O(nlog(n))。如果有人能解釋這一點，我將不勝感激。
uj5u.com熱心網友回復：
至少有兩種方式來看待這個問題：
一棵完全二叉樹有 O(??) 個葉子。
想象一個有 31 個元素的堆。這代表一棵完美的二叉樹——底層是滿的。底層有 16 個元素，(?? 1)/2。這意味著在最壞的情況下，接下來的 16 次洗掉將代表相同數量的交換。
概括地說，要洗掉大約一半的節點，我們需要執行 O(??/2 log??) 交換，即 O(??log??)
O(log??!) = O(??log??)
請參閱此問答以獲得證明。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/532365.html
標籤：算法时间复杂度大哥堆排序