heap sort的最佳狀況??

我知道他的複雜度都是nlogn

但是什麼狀況是最佳

什麼狀況是最差

能有人能深論heap sort給我了解嗎

感謝

越多關於heap sort的資料最好 再三感謝

已更新項目:

heap sort的複雜度可以分為2點 第一建構初始heap的複雜度第二heap逐步排序的複雜度

那麼我想說是否能再建構的時候 也就是輸入資料的順序即為產生最大堆積的順序

也就是省略調建構初始heap的複雜度 只有逐步排序的複雜度 這樣是最佳狀況嗎

1 個解答

評分
  • Leslie
    Lv 7
    10 年前
    最佳解答

    假設 heap-sort 是用 max-heap 的資料結構.

    底下是直觀 (粗略) 的分析.

    (底下我都用大 O, 其實有的地方, 用 Omega 或 THETA 才對)一個演算法, 若最差情況和最佳情況的複雜度相等, 則就無所謂最差情況和最佳情況了,

    因為每一種輸入都是一般情況, 無特殊情況. (因此您的問題怪怪的, 嘻 :-)但一般分析 heap-sort, 都是先找最差情況,

    因為這樣才容易說明及了解,

    但是會發現最差情況也是一般共同的表現 (書上把這一部分省略,

    因為嚴謹的分析是很煩的, 而直觀的分析又會有缺失之處, 易受攻擊).heap-sort 有兩階段,

    第一階段是把 n 個數造成 max-heap.

    這若是用 bottom-up 建造, 是 O(n).

    若是用 top-down 建造, 是 O(n) (最佳情況, 譬如, 當輸入資料是由大到小時)

    到 O(nlogn) (最差情況, 譬如, 當輸入資料是由小到大時).

    這部份我們可不管, 因為第二階段反正都要 O(nlogn).第二階段是對 max-heap H[1...n] 做 n-1 次的 root-deletion.

    (i=n, n-1, ..., 2) 每次 root-deletion, 是將 root 和 最後一個數 H[i] 對調,

    然後把 H[1...(i-1)] heapify (把新的 root 調降至適當位置).

    heapify 最多要花 log(i) 的時間, 因此說, 最差情況是

    Sigma(log(i)) (即, log(n)+log(n-1)+...+1).但是, 真的存在每次都會花 log(i) 的情況嗎? 直覺是對的,

    而且, 這並非只有一些情況, 而是所有情況:

    因為 max-heap 感覺上是一層一層的數, 越下層越小的,

    因此 root (最大) 和 最後一個數 H[i] (直覺是夠小的) 對調後,

    新的 (很小的) root 要一層一層調降到底 (高度 log(i)), 須 log(i) 次.

    這沒有所謂最差, 平均或最佳情況, 而是一般共同的情況.底下是用直觀說明 Sigma(log(i))=O(nlogn):

    一個 max-heap 是第一層 1 個數, 第二層 2 個, 第三層 4 個, ......,

    若是 n 個數的 max-heap, 幾乎有一半或更多的數, 都在最下兩層中.

    因此, Sigma(log(i)) >= (n/2)(logn-1)=O(nlogn)

    另外, 顯然 Sigma(log(i)) <= n(logn+1)=O(nlogn)

    因此 Sigma(log(i))=O(nlogn)

    2010-11-25 20:38:41 補充:

    > ... 也就是省略調建構初始heap的複雜度 只有逐步排序的複雜度 這樣是最佳狀況嗎?

    省了第一階段的時間, 但第二階段還是 nlogn, 整個時間還是 nlogn.

    不管輸入為何, 此 heap sort 都是 nlogn 的複雜度. 因此,

    這演算法沒有分最佳及最差, 因為任何輸入情況都是花一樣的時間複雜度.

    ----------

    隨便給 n 個數, 由 (x1+x2+x3+...+xn)/n 來求平均值,

    有所謂的最佳及最差情況嗎?

    如果大家錢都一樣多, 能找出所謂的最富及最窮的人嗎?

還有問題?馬上發問,尋求解答。