并不需要復雜的數學就能證明你可以逐漸趨近的速度有多快。
• 來源：linux.cn • 作者：Simon Arneaud • 譯者：SilentDawn •
（本文字數：3283，閱讀時長大約：5 分鐘）
基本上所有正而八經的算法教材都會解釋像 快速排序(quicksort)和 堆排序(heapsort)這樣的排序算法有多快，但并不需要復雜的數學就能證明你可以逐漸趨近的速度有多快。
關于標記的一個嚴肅說明：
大多數計算機專業的科學家使用大寫字母 O 標記來指代“趨近，直到到達一個常數比例因子”，這與數學專業所指代的意義是有所區別的。這里我使用的大 O 標記的含義與計算機教材所指相同，但至少不會和其他數學符號混用。
基于比較的排序
先來看個特例，即每次比較兩個值大小的算法（快速排序、堆排序，及其它通用排序算法）。這種思想后續可以擴展至所有排序算法。
一個簡單的最差情況下的計數角度
假設有 4 個互不相等的數，且順序隨機，那么，可以通過只比較一對數字完成排序嗎？顯然不能，證明如下：根據定義，要對該數組排序，需要按照某種順序重新排列數字。換句話說，你需要知道用哪種排列方式？有多少種可能的排列？第一個數字可以放在四個位置中的任意一個，第二個數字可以放在剩下三個位置中的任意一個，第三個數字可以放在剩下兩個位置中的任意一個，最后一個數字只有剩下的一個位置可選。這樣，共有 4×3×2×1=4!=24 種排列可供選擇。通過一次比較大小，只能產生兩種可能的結果。如果列出所有的排列，那么“從小到大”排序對應的可能是第 8 種排列，按“從大到小”排序對應的可能是第 24 種排列，但無法知道什么時候需要的是其它 22 種排列。
通過 2 次比較，可以得到 2×2=4 種可能的結果，這仍然不夠。只要比較的次數少于 5（對應 2^5 = 32 種輸出），就無法完成 4 個隨機次序的數字的排序。如果 W(N) 是最差情況下對 N 個不同元素進行排序所需要的比較次數，那么，
兩邊取以 2 為底的對數，得：
N! 的增長近似于 N^N （參閱 Stirling 公式 ），那么，
這就是最差情況下從輸出計數的角度得出的 O(N log N) 上限。
從信息論角度的平均狀態的例子
使用一些信息論知識，就可以從上面的討論中得到一個更有力的結論。下面，使用排序算法作為信息傳輸的編碼器：
- 任取一個數，比如 15
- 從 4 個數字的排列列表中查找第 15 種排列
- 對這種排列運行排序算法，記錄所有的“大”、“小”比較結果
- 用二進制編碼發送比較結果
- 接收端重新逐步執行發送端的排序算法，需要的話可以引用發送端的比較結果
- 現在接收端就可以知道發送端如何重新排列數字以按照需要排序，接收端可以對排列進行逆算，得到 4 個數字的初始順序
- 接收端在排列表中檢索發送端的原始排列，指出發送端發送的是 15
確實，這有點奇怪，但確實可以。這意味著排序算法遵循著與編碼方案相同的定律，包括理論所證明的不存在通用的數據壓縮算法。算法中每次比較發送 1 比特的比較結果編碼數據，根據信息論，比較的次數至少是能表示所有數據的二進制位數。更技術語言點， 平均所需的最小比較次數是輸入數據的香農熵，以比特為單位 。熵是衡量信息等不可預測量的數學度量。
包含 N 個元素的數組，元素次序隨機且無偏時的熵最大，其值為 log2 N! 個比特。這證明 O(N log N) 是一個基于比較的對任意輸入排序的最優平均值。
以上都是理論說法，那么實際的排序算法如何做比較的呢？下面是一個數組排序所需比較次數均值的圖。我比較的是理論值與快速排序及 Ford-Johnson 合并插入排序 的表現。后者設計目的就是最小化比較次數（整體上沒比快速排序快多少，因為生活中相對于最大限度減少比較次數，還有更重要的事情）。又因為 合并插入排序(merge-insertion sort)是在 1959 年提出的，它一直在調整，以減少了一些比較次數，但圖示說明，它基本上達到了最優狀態。
一點點理論導出這么實用的結論，這感覺真棒！
小結
證明了：
- 如果數組可以是任意順序，在最壞情況下至少需要 O(N log N) 次比較。
- 數組的平均比較次數最少是數組的熵，對隨機輸入而言，其值是 O(N log N) 。
注意，第 2 個結論允許基于比較的算法優于 O(N log N)，前提是輸入是低熵的（換言之，是部分可預測的）。如果輸入包含很多有序的子序列，那么合并排序的性能接近 O(N)。如果在確定一個位之前，其輸入是有序的，插入排序性能接近 O(N)。在最差情況下，以上算法的性能表現都不超出 O(N log N)。
一般排序算法
基于比較的排序在實踐中是個有趣的特例，但從理論上講，計算機的 CMP 指令與其它指令相比，并沒有什么特別之處。在下面兩條的基礎上，前面兩種情形都可以擴展至任意排序算法：
- 大多數計算機指令有多于兩個的輸出，但輸出的數量仍然是有限的。
- 一條指令有限的輸出意味著一條指令只能處理有限的熵。
這給出了 O(N log N) 對應的指令下限。任何物理上可實現的計算機都只能在給定時間內執行有限數量的指令，所以算法的執行時間也有對應 O(N log N) 的下限。
什么是更快的算法？
一般意義上的 O(N log N) 下限，放在實踐中來看，如果聽人說到任何更快的算法，你要知道，它肯定以某種方式“作弊”了，其中肯定有圈套，即它不是一個可以處理任意大數組的通用排序算法。可能它是一個有用的算法，但最好看明白它字里行間隱含的東西。
一個廣為人知的例子是 基數排序(radix sort)算法，它經常被稱為 O(N) 排序算法，但它只能處理所有數字都能放入 k 比特的情況，所以實際上它的性能是 O(kN)。
什么意思呢？假如你用的 8 位計算機，那么 8 個二進制位可以表示 2^8=256 個不同的數字，如果數組有上千個數字，那么其中必有重復。對有些應用而言這是可以的，但對有些應用就必須用 16 個二進制位來表示，16 個二進制位可以表示 2^16=65,536 個不同的數字。32 個二進制位可以表示 2^32=4,294,967,296 不同的數字。隨著數組長度的增長，所需要的二進制位數也在增長。要表示 N 個不同的數字，需要 k ≥ log2? N 個二進制位。所以，只有允許數組中存在重復的數字時， O(kN) 才優于 O(N log N)。
一般意義上輸入數據的 O(N log N) 的性能已經說明了全部問題。這個討論不那么有趣因為很少需要在 32 位計算機上對幾十億整數進行排序， 如果有誰的需求超出了 64 位計算機的極限，他一定沒有告訴別人 。
via: theartofmachinery.com
作者： Simon Arneaud 選題： lujun9972 譯者： silentdawn-zz 校對： wxy
本文由 LCTT 原創編譯， Linux中國 榮譽推出
