動機
合併排序和堆排序在最壞情況下使用 次比較。這個代價只是這兩種算法的偶然現象,還是所有基於比較的排序方法都無法繞開的障礙?決策樹把算法可能出現的各種比較結果轉化為一個計數問題:必須存在足夠多不同的結果,才能區分各種可能的輸入次序。
模型的選擇至關重要。當鍵值落在適當細小的整數範圍內時,計數排序可以在線性時間內運行,因為它利用鍵值作為陣列索引。下界假設比較是取得鍵值次序資訊的唯一途徑,因此計數排序並不是該下界的反例。
定義
定義 1.8.1
(確定性比較排序算法)
確定性比較排序算法接收 個互不相同的鍵,並且對每一種輸入次序都必須按遞增次序輸出這些鍵。其控制流程可以依賴鍵與鍵之間兩兩比較的結果。我們統計的是鍵的比較次數,而不是移動次數,也不是與鍵值無關的算術運算。對於互不相同的鍵,一次比較有兩種可能的結果:小於或大於。
定義 1.8.2
(比較排序的決策樹)
比較決策樹中,每個內部節點對應算法在該時刻可能進行的一次比較,每種結果對應一條出邊。葉記錄在觀察到相應結果之後所選定的輸出次序。不同分支的長度可以不同;從根到葉的最大長度即最壞情況下的比較次數。
定理
定理 1.8.3
(比較排序需要大量比較)
對 個互不相同的鍵進行排序的每個確定性比較排序算法,都存在一個最壞輸入,至少需要 次比較。因此其最壞情況比較次數為 。
定理 1.8.4
(有界整數鍵的計數排序)
對於取值於 ()的 個整數鍵,在下文所述的陣列索引模型中,計數排序可以在 時間和 輔助空間內產生穩定的有序輸出。
證明:統計葉的數目
證明
(統計決策樹的葉)
個互不相同的輸入位置共有 種可能的相對次序。正確的比較算法必須區分所有這些次序。如果兩種不同的相對次序到達同一片葉,算法對二者就會輸出相同的輸入位置排列。由於這兩種次序對應的正確遞增位置排列不同,至少有一個輸出是錯誤的。
高度為 的二叉樹至多有 片葉。即使某些葉出現在深度小於 處,這一結論仍然成立:可以在概念上把每條較短的路徑延伸到深度 ,也可以用歸納法證明該界。因此,對全部 種次序都正確的決策樹必須滿足 ,從而 。
要得到初等的漸近界:當 時, 的因子中至少有 個不小於 。於是 ,其以 2 為底的對數為 。上界 則由每個因子至多為 得出。因此資訊量需求的量級為 。
證明透視
為甚麼兩種次序不能共用一片葉
證明有三個環節。第一,葉只固定一個輸出排列,因為算法只看到了通往該葉的路徑上的比較結果。第二,鍵互不相同,所以不同的相對次序需要不同的輸出排列;用到「互不相同」的正是這一步。因此至少存在 片不同的葉。第三,把計數轉成時間界的是 :二叉樹至多有 片葉,所以葉很多就迫使高度很大。
每個環節都可以問:少了它會怎樣。若算法可以直接讀取鍵值(而不只是比較),葉就不再由一串二元結果組成的路徑決定,葉的數目也就不能限制執行時間。若容許相等的鍵,需要的不同輸出便少於 個。證明並沒有指出較深的葉在哪裏,只說明存在這樣一片葉。
計數排序與穩定性
定義 1.8.5
(穩定排序)
若一個排序算法在輸出中保持鍵相同的記錄在輸入中的相對次序,則稱它為穩定的。
對每個鍵值 ,統計輸入中有多少項具有該鍵值。計算前綴總和 ,即鍵不超過 的項數。由右至左掃描輸入。對於鍵為 的一項,以零為起始索引,把它放到輸出位置 ,然後將 減 1。
證明
(計數排序正確、穩定,代價為 O(n+K))
為鍵 預留的位置恰好是一段連續區間,位於所有較小鍵的位置之後、所有較大鍵的位置之前。每一項佔用該區間內一個尚未使用的位置,因此輸出是有序的,且每個輸入項恰好出現一次。由右至左掃描會由右至左填充該區間:若兩個鍵相同的項在輸入中以某一次序出現,則較後的那一項被放在較後的輸出位置。它們的相對次序得以保持,這就是穩定性。
初始化計數陣列和計算前綴總和的代價為 ;計數和輸出放置的代價為 。計數陣列使用 空間,輸出陣列使用 空間。這裏假定按鍵索引的代價為常數時間,並且保證鍵是所述範圍內的整數。範圍大小 是代價的一部分:若 相對於 非常大,該算法不一定比比較排序更快或更省空間。
例題詳解
例題 1.8.6
(三個互不相同的鍵)
共有 種可能的次序。高度為 2 的二叉比較樹至多有四片葉,所以某些輸入至少需要 次比較。三次比較總是足夠的,例如先比較兩個鍵,再把第三個鍵插入到它們已排好的序對中。
例題 1.8.7
(對一個細小陣列計數)
對於鍵 且 ,鍵值 的計數為 。前綴總和為 。它們預留的輸出位置是:鍵 0 佔位置 ,鍵 1 佔位置 ,鍵 2 佔位置 。輸出的鍵為 。
例題 1.8.8
(相等的鍵保持原有次序)
設上例中兩個鍵為 2 的項按輸入次序分別標記為 和 。由右至左掃描時,先把 放在位置 3,之後把 放在位置 2。它們的輸出次序為 ,所以相關記錄保持穩定。
例題 1.8.9
(範圍很大會改變得失權衡)
當 且保證鍵在大小為 的範圍內時,計數陣列需要十億個項目。 這個界是正確的,但其中的 項佔主導地位。比較排序則可以避免為每個可能的鍵值分配一個計數器。
常見錯誤
反例模式
線性時間的整數排序並不反駁決策樹下界
一個誘人的說法是:每個排序算法都需要 步。計數排序在鍵範圍很小時就推翻了它。取 個鍵,取值於 ,即 。計數排序的步數為 ,而 ,所以比較排序在某些輸入上至少需要 次比較。這並不矛盾,因為決策樹的證明只統計對鍵的二元比較,計數排序卻把每個整數鍵當作陣列索引來讀取,一步操作就能在 個值之間作出區分。它獲得了比較模型以外的資訊,所以下界的假設並不適用。正確的說法是受限制的版本:只靠比較來排序任意互不相同的鍵,需要 次比較。
常見錯誤
(最壞情況下界不是對每個輸入的下界)
最壞情況比較次數的下界並不表示每個輸入都需要那麼多次比較。自適應算法可能很快識別出某些已經有序的輸入,卻仍然在另一個輸入上需要大量比較。該下界也沒有計入移動大型記錄或分配記憶體所花費的時間。
常見錯誤
(計數 n! 預設鍵互不相同)
下界使用互不相同的鍵,以保證有 種不同的所需相對次序。相等的鍵會減少可區分次序的數目,而穩定性對鍵相同的記錄另有要求。對於必須處理所有輸入的算法,這族互不相同的困難輸入已足以確立最壞情況下界。
模型揭示了甚麼
決策樹抽象掉了算法選擇的具體比較。一個算法可能比較相鄰的鍵,另一個可能比較相距很遠的鍵,它們的樹形狀可以大相徑庭。葉的數目同時約束所有這些算法,因為每個二元結果至多使可區分的分支數加倍。
證明並不要求樹是平衡的。某個輸入對應的葉很淺,就會使可供其他眾多次序使用的淺路徑變少。高度界說明至少有一條路徑很長,但並沒有指出對於具體某個算法,哪個輸入會實現這條路徑。
對於有界整數鍵,模型提供的不止是比較。鍵值直接選定 個計數器之一,而算法要為這些計數器的初始化和遍歷付出代價。這兩種分析可以並存:一種證明了在對鍵的存取受限時的局限,另一種利用更強的操作並核算其記憶體範圍。
概念視角分析
連常數也保留的同一個界
Stirling 公式給出
所以資訊界是 ,而不只是 。當 時右邊約為 ,與上文所用的值吻合。
平均深度與隨機化算法
同樣的計數思想也可以約束在均勻隨機輸入次序上的平均比較次數。設 種可能的次序終止於深度為 的葉。對於任意二叉樹,葉權重滿足 。一種證明是:給根賦權重 1,並把每個節點的權重平均分給它的兩個子節點;所有葉的權重之和至多等於初始權重。
算術-幾何平均不等式給出
取以 2 為底的對數並整理,得到 。因此,對於每個確定性比較排序,即使在均勻選取的互不相同鍵的次序上取平均,也至少需要 次比較。這比僅僅說有一條路徑具有該長度的結論更強。
現在考慮一個隨機化比較排序,它對每個輸入和每種隨機選擇都正確,並且比較次數和隨機位元數都有固定的有限上界。固定其隨機位元:得到的確定性比較樹仍然對每種輸入次序正確排序。它在均勻輸入分佈下的平均深度至少為 。對隨機位元取平均保持這一不等式。因此,至少存在一個固定的輸入次序,其期望比較次數至少為 ,其中餘下的期望是對算法自身的隨機選擇而取的。這一論證並不聲稱每個輸入都有這樣的期望代價。
比較次數和隨機位元數都有固定的有限上界,使得所有平均都是普通的有限和。更一般的幾乎必然終止的隨機化算法可以借助額外的極限論證來處理,但這裏陳述的版本並不需要這些。均勻分佈只是用來找出一個困難的固定輸入的證明手段,並不是對現實世界輸入所作的假設。
記錄與取值範圍編碼的代價核算
計數排序通常用來排序帶有附屬數據的記錄,例如附在整數分數上的姓名。穩定性針對的正是這些記錄:分數相同的記錄必須保持其原有次序。計數陣列存放各鍵值的計數;輸出陣列存放記錄或指向記錄的參照。如果複製整條記錄的代價超過一個單位,就必須把這一表示細節計入操作代價。
參數 是鍵的全集的大小,而不是恰好出現的相異鍵的個數。如果鍵的範圍從已知的整數最小值 到最大值 ,減去 後得到從 0 到 的索引,陣列長度為 。計算或儲存一個龐大的範圍,其代價可能超過輸入規模。在位元模型中,表示一個鍵並對其作算術運算的代價也可能超過一個單位;所述的界針對的是字組層級的陣列索引模型。
比較算法可以利用特定輸入中已有的次序,整數算法可以利用較小的鍵全集。這是兩種不同的結構來源。只要任意互不相同的鍵只能透過二元比較來排序,最壞情況下界就依然適用,即使個別輸入恰好很容易。
當 或 時,只有一種相對次序,下界為零次比較。漸近陳述針對的是 增大的情形,並不要求在零處計算 。類似地,當 時,計數排序可以直接返回空輸出,但仍需為任何明確初始化的計數陣列付出代價。
總結
比較排序的決策樹必須有足夠多的葉來區分 種次序,由此得到最壞情況 的比較次數下界。計數排序在另一種模型下利用整數的直接索引,以 時間運行,並透過反向遍歷獲得穩定性。
練習
快速檢查
(高度為四的二叉決策樹至多有多少片葉?)
每一層至多令分支數加倍。
解答 · 答案
至多 片。有些葉可能位於較小的深度,但這不會使最大值增加。
快速檢查
(對四個互不相同的鍵排序,葉論證給出甚麼下界?)
數出相對次序的個數,再與二的冪比較。
解答 · 答案
共有 種相對次序。由於 ,某些輸入至少需要五次比較。
快速檢查
(對於鍵 ,給出計數陣列和排序後的鍵序列。)
鍵範圍為 ,即 。
解答 · 答案
對於鍵範圍 ,計數為 ,排序後的鍵為 。
快速檢查
(為甚麼在計數排序中由右至左掃描輸入能保持鍵相同的記錄的次序?)
想想鍵相同的記錄中哪一個先被放置。
解答 · 答案
隨著前綴計數器遞減,每個鍵的輸出區間由右至左被填充。輸入中較後的記錄先被遇到,並獲得較後的位置,所以較前的記錄在輸出中仍然較前。