Comparison & Swap

發表於 Disqus：
文章字數： 584 所需閱讀時間 ≈ 1 分鐘

排序方法能達到多快 ?

假設排序方法的設計是採用 Comparison & Swap 技巧

  • 利用決策樹 (Decision Tree) 來判斷:
    • Decision Tree: 描述 Sort 過程中，各種狀況的比較過程
      • Non-leaf Node: 表示 “Comparison”
      • 左、右分枝: 表示 “Yes” or “No”
      • Leaf: 排序結果
  • 例:試說明 3 個資料 a，b，c 排序之 Decision Tree

說明

  • n 個資料做 Sort，有 n! 個可能的排序結果。因此，Sort 的 Decision Tree 有 n! 個 Leaf nodes
  • 根據二元樹之定理: 二元樹中，第 i 個 level 的 node 個數最多有 \(2^{i-1}\) 個
    • ∴ \(2^{i-1} = n!\) ⇒ \(i-1 = \lceil \log_2n!\rceil\) ⇒ \(i = \lceil \log_2n!\rceil + 1\)，表示此 Tree 的高度至少為\(\lceil \log_2n!\rceil + 1\)
  • 比較次數為 \(\geq \lceil \log_2n!\rceil\)
  • 又 \(n! \geq {\frac{n}{2}}^{\frac{n}{2}}\) ⇒ \(\lceil \log_2n!\rceil \geq \log{\frac{n}{2}}^{\frac{n}{2}} = \frac{n}{2}\log\frac{n}{2} \leq O(n\log n)\)

參考資料