[[341282]]

基本上所有正而八經(jīng)的算法教材都會解釋像快速排序quicksort和堆排序heapsort這樣的排序算法有多快，但并不需要復(fù)雜的數(shù)學(xué)就能證明你可以逐漸趨近的速度有多快。

關(guān)于標(biāo)記的一個嚴(yán)肅說明：

大多數(shù)計算機專業(yè)的科學(xué)家使用大寫字母 O 標(biāo)記來指代“趨近，直到到達一個常數(shù)比例因子”，這與數(shù)學(xué)專業(yè)所指代的意義是有所區(qū)別的。這里我使用的大 O 標(biāo)記的含義與計算機教材所指相同，但至少不會和其他數(shù)學(xué)符號混用。

基于比較的排序

先來看個特例，即每次比較兩個值大小的算法（快速排序、堆排序，及其它通用排序算法）。這種思想后續(xù)可以擴展至所有排序算法。

一個簡單的最差情況下的計數(shù)角度

假設(shè)有 4 個互不相等的數(shù)，且順序隨機，那么，可以通過只比較一對數(shù)字完成排序嗎？顯然不能，證明如下：根據(jù)定義，要對該數(shù)組排序，需要按照某種順序重新排列數(shù)字。換句話說，你需要知道用哪種排列方式？有多少種可能的排列？第一個數(shù)字可以放在四個位置中的任意一個，第二個數(shù)字可以放在剩下三個位置中的任意一個，第三個數(shù)字可以放在剩下兩個位置中的任意一個，最后一個數(shù)字只有剩下的一個位置可選。這樣，共有  4×3×2×1=4!=24 種排列可供選擇。通過一次比較大小，只能產(chǎn)生兩種可能的結(jié)果。如果列出所有的排列，那么“從小到大”排序?qū)?yīng)的可能是第 8 種排列，按“從大到小”排序?qū)?yīng)的可能是第 24 種排列，但無法知道什么時候需要的是其它 22 種排列。

通過 2 次比較，可以得到 2×2=4 種可能的結(jié)果，這仍然不夠。只要比較的次數(shù)少于 5（對應(yīng) 2⁵ = 32  種輸出），就無法完成 4 個隨機次序的數(shù)字的排序。如果 W(N) 是最差情況下對 N 個不同元素進行排序所需要的比較次數(shù)，那么，

兩邊取以 2 為底的對數(shù)，得：

N! 的增長近似于 NN （參閱 Stirling 公式），那么，

這就是最差情況下從輸出計數(shù)的角度得出的 O(N log N) 上限。

從信息論角度的平均狀態(tài)的例子

使用一些信息論知識，就可以從上面的討論中得到一個更有力的結(jié)論。下面，使用排序算法作為信息傳輸?shù)木幋a器：

1. 任取一個數(shù)，比如 15
2. 從 4 個數(shù)字的排列列表中查找第 15 種排列
3. 對這種排列運行排序算法，記錄所有的“大”、“小”比較結(jié)果
4. 用二進制編碼發(fā)送比較結(jié)果
5. 接收端重新逐步執(zhí)行發(fā)送端的排序算法，需要的話可以引用發(fā)送端的比較結(jié)果
6. 現(xiàn)在接收端就可以知道發(fā)送端如何重新排列數(shù)字以按照需要排序，接收端可以對排列進行逆算，得到 4 個數(shù)字的初始順序
7. 接收端在排列表中檢索發(fā)送端的原始排列，指出發(fā)送端發(fā)送的是 15

確實，這有點奇怪，但確實可以。這意味著排序算法遵循著與編碼方案相同的定律，包括理論所證明的不存在通用的數(shù)據(jù)壓縮算法。算法中每次比較發(fā)送 1 比特的比較結(jié)果編碼數(shù)據(jù)，根據(jù)信息論，比較的次數(shù)至少是能表示所有數(shù)據(jù)的二進制位數(shù)。更技術(shù)語言點，平均所需的最小比較次數(shù)是輸入數(shù)據(jù)的香農(nóng)熵，以比特為單位。熵是衡量信息等不可預(yù)測量的數(shù)學(xué)度量。

包含 N 個元素的數(shù)組，元素次序隨機且無偏時的熵最大，其值為 log2​ N! 個比特。這證明 O(N log N) 是一個基于比較的對任意輸入排序的最優(yōu)平均值。

以上都是理論說法，那么實際的排序算法如何做比較的呢？下面是一個數(shù)組排序所需比較次數(shù)均值的圖。我比較的是理論值與快速排序及 Ford-Johnson 合并插入排序 的表現(xiàn)。后者設(shè)計目的就是最小化比較次數(shù)（整體上沒比快速排序快多少，因為生活中相對于最大限度減少比較次數(shù)，還有更重要的事情）。又因為合并插入排序merge-insertion sort是在 1959 年提出的，它一直在調(diào)整，以減少了一些比較次數(shù)，但圖示說明，它基本上達到了最優(yōu)狀態(tài)。

一點點理論導(dǎo)出這么實用的結(jié)論，這感覺真棒！

小結(jié)

證明了：

1. 如果數(shù)組可以是任意順序，在最壞情況下至少需要 O(N log N) 次比較。
2. 數(shù)組的平均比較次數(shù)最少是數(shù)組的熵，對隨機輸入而言，其值是 O(N log N) 。

注意，第 2 個結(jié)論允許基于比較的算法優(yōu)于 O(N log N)，前提是輸入是低熵的（換言之，是部分可預(yù)測的）。如果輸入包含很多有序的子序列，那么合并排序的性能接近 O(N)。如果在確定一個位之前，其輸入是有序的，插入排序性能接近 O(N)。在最差情況下，以上算法的性能表現(xiàn)都不超出 O(N log N)。

一般排序算法

基于比較的排序在實踐中是個有趣的特例，但從理論上講，計算機的 CMP 指令與其它指令相比，并沒有什么特別之處。在下面兩條的基礎(chǔ)上，前面兩種情形都可以擴展至任意排序算法：

1. 大多數(shù)計算機指令有多于兩個的輸出，但輸出的數(shù)量仍然是有限的。
2. 一條指令有限的輸出意味著一條指令只能處理有限的熵。

這給出了 O(N log N) 對應(yīng)的指令下限。任何物理上可實現(xiàn)的計算機都只能在給定時間內(nèi)執(zhí)行有限數(shù)量的指令，所以算法的執(zhí)行時間也有對應(yīng) O(N log N) 的下限。

什么是更快的算法？

一般意義上的 O(N log N) 下限，放在實踐中來看，如果聽人說到任何更快的算法，你要知道，它肯定以某種方式“作弊”了，其中肯定有圈套，即它不是一個可以處理任意大數(shù)組的通用排序算法?？赡芩且粋€有用的算法，但最好看明白它字里行間隱含的東西。

一個廣為人知的例子是基數(shù)排序radix sort算法，它經(jīng)常被稱為 O(N) 排序算法，但它只能處理所有數(shù)字都能放入 k 比特的情況，所以實際上它的性能是 O(kN)。

什么意思呢？假如你用的 8 位計算機，那么 8 個二進制位可以表示 2⁸=256 個不同的數(shù)字，如果數(shù)組有上千個數(shù)字，那么其中必有重復(fù)。對有些應(yīng)用而言這是可以的，但對有些應(yīng)用就必須用 16 個二進制位來表示，16 個二進制位可以表示 2¹⁶=65,536 個不同的數(shù)字。32 個二進制位可以表示 2³²=4,294,967,296 不同的數(shù)字。隨著數(shù)組長度的增長，所需要的二進制位數(shù)也在增長。要表示 N 個不同的數(shù)字，需要 k ≥ log2​ N 個二進制位。所以，只有允許數(shù)組中存在重復(fù)的數(shù)字時， O(kN) 才優(yōu)于 O(N log N)。

一般意義上輸入數(shù)據(jù)的 O(N log N) 的性能已經(jīng)說明了全部問題。這個討論不那么有趣因為很少需要在 32 位計算機上對幾十億整數(shù)進行排序，如果有誰的需求超出了 64 位計算機的極限，他一定沒有告訴別人。