http://blog.csdn.net/linuxtiger/article/details/7172258

如果僅從代碼上直觀觀察，會得出構造二叉堆的時間復雜度為O(n㏒n)的結果，這個結果是錯的，雖然該算法外層套一個n次循環，而內層套一個分治策略下的㏒n復雜度的循環，該思考方法犯了一個原則性錯誤，那就是構建二叉堆是自下而上的構建，每一層的最大縱深總是小于等于樹的深度的，因此，該問題是疊加問題，而非遞歸問題。那么換個方式，假如我們自上而下建立二叉堆，那么插入每個節點都和樹的深度有關，并且都是不斷的把樹折半來實現插入，因此是典型的遞歸，而非疊加。

在做證明之前，我們的前提是，建立堆的順序是bottom-top的。

正確的證明方法應當如下：

1. 具有n個元素的平衡二叉樹，樹高為㏒n，我們設這個變量為h。

2. 最下層非葉節點的元素，只需做一次線性運算便可以確定大根，而這一層具有2^(h-1)個元素，我們假定O(1)=1，那么這一層元素所需時間為2^(h-1)?× 1。

3. 由于是bottom-top建立堆，因此在調整上層元素的時候，并不需要同下層所有元素做比較，只需要同其中之一分支作比較，而作比較次數則是樹的高度減去當前節點的高度。因此，第x層元素的計算量為2^(x)?× (h-x)。

4. 又以上通項公式可得知，構造樹高為h的二叉堆的精確時間復雜度為：

S = 2^(h-1)?× 1 + 2^(h-2)?× 2 + …… +1?× (h-1) ?①

通過觀察第四步得出的公式可知，該求和公式為等差數列和等比數列的乘積，因此用錯位想減發求解，給公式左右兩側同時乘以2，可知：

2S = 2^h?× 1 +?2^(h-1)?× 2+ …… +2?× (h-1) ? ? ?②

用②減去①可知： S =2^h?× 1 - h +1 ? ? ? ?③

將h =?㏒n 帶入③，得出如下結論：

S = n -?㏒n +1 = O(n)

結論：構造二叉堆的時間復雜度為線性得證。

上題有些小細節推導錯誤，整體思路是對的

總結

以上是生活随笔為你收集整理的构建二叉堆时间复杂度的证明的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。