動機
快速排序選取一個主元,將其餘元素圍繞它劃分,然後遞歸地對兩側排序。如果每一步都恰好選到很差的主元,就會產生二次方的工作量。隨機選取主元並不能排除這種執行過程,但它使我們能夠對任意固定輸入,就算法自身的隨機選擇來量化其平均成本。
我們不直接求解遞推式,而是提出一個更局部的問題:對於已知排序名次的兩個元素,它們在整個執行過程中被比較的概率是多少?把這些概率相加,即得到期望比較次數的精確值。證明還說明了為甚麼各個鍵對比較事件之間不需要獨立性。
定義
定義 1.9.1
(配對指示變量與比較次數)
輸入由比較模型中的 個互不相同的鍵組成。在每個含有 個鍵的遞歸調用中,從這些鍵中均勻隨機地選取一個主元;在給定當前子問題的條件下,該選擇與以往的隨機選擇互相獨立。將該子問題中其餘每個鍵各與主元比較一次,把較小的鍵放在一側、較大的鍵放在另一側,然後遞歸地對兩側排序。規模為零或一的調用不進行任何比較。
設排序後的鍵為 。對每個 ,若 與 在執行過程中被比較,則令 為一,否則為零。設 為按上述劃分規則所作的鍵比較總次數。當 時記 ,並規定 。
定理
定理 1.9.2
(鍵對比較概率)
對每一對 , 與 被比較的概率為 。
定理 1.9.3
(期望比較次數的精確值)
對 ,隨機化快速排序的期望鍵比較次數為
其中約定 。特別地,該期望為 。
證明:哪個主元會分隔一對鍵?
證明
(只有區間中的第一個主元才起作用)
考慮名次區間 。在該區間內沒有任何鍵被選為主元之前,區間內所有鍵始終留在同一個遞歸子問題中。名次較小的主元會把整個區間送往較大的一側;名次較大的主元會把整個區間送往較小的一側。因此,區間之外的主元不可能把兩個端點分開。
當區間內的第一個主元被選出時,有兩種可能。若它是 或 ,則另一個端點處於同一子問題中,並與該主元比較。若它是內部的鍵,則兩個端點被送入相反的遞歸子問題,此後永遠不會被比較。任何一對鍵至多被比較一次,因為其中一個端點被選為主元之後,就不再出現在遞歸調用中。
區間內第一個被選中的主元在其 個鍵中服從均勻分佈。理解這一點的一種方式是:預先給鍵分配一個均勻隨機的優先級順序,並始終以子問題中優先級最小的鍵為主元。這樣得到的主元在每個當前子問題中都是均勻的,而且任意固定子集中優先級最先的鍵屬於其中任一成員的可能性相同。等價地說,對區間之外的主元反覆取條件,並不破壞區間內各鍵之間的對稱性。區間內恰有兩個鍵是端點,因此所求概率為 。
證明透視
區間內的第一個主元
名次區間之外的主元使兩個端點保持在一起。端點作主元時完成它們唯一的一次比較;內部的鍵作主元則將它們永久分開。區間內各鍵之間的均勻對稱性因此把概率計算歸結為:在區間大小所對應的鍵數中,有兩個有利的鍵。
證明:對指示變量求和
證明
(對配對概率求和)
每次比較都發生在一個主元與另一個鍵之間,且沒有任何一對鍵被比較兩次。因此 。由期望的線性性(它並不要求這些指示變量互相獨立),
對於區間長度 ,具有該區間長度的鍵對共有 個。因此,當 時,
當 時,按約定兩邊都為零。對 ,積分界 給出漸近上界。調和和的增長階也至少為 ,因此當 足夠大時,期望比較次數為 。
正確性與成本模型
在每個遞歸調用中,放在主元左側的每個鍵都較小,放在右側的每個鍵都較大。對子問題規模用歸納法可知兩個遞歸結果都已排好序;把排好序的左側、主元與排好序的右側串接起來,就得到按順序排列的全部輸入鍵。每次調用都把其主元從後續遞歸中移除,因此對任何主元序列算法都會終止。
該精確定理計算的是在所述劃分過程下的鍵比較次數。若劃分對每個被檢查的鍵只做常數量的額外工作,且主元可在常數時間內取樣,則在該模型下總的期望執行時間為 。具體實作必須自行計入主元生成的成本與儲存。該期望是對固定輸入上的隨機主元選擇而取的;它並不假定輸入本身是隨機排列的。
最壞的主元序列是反覆選取最小值或最大值,此時共進行 次比較。不利情形出現的概率也許很小,但期望界並不禁止它發生。
概念視角結構
遞歸樹是一棵隨機二叉搜尋樹
把每個主元記為其子問題的根,兩側子問題的主元作為它的子節點。這是 上的二叉搜尋樹,而每個鍵與其上方的每個主元恰好比較一次。因此 當且僅當 之一是另一個的祖先,而 就是所有節點深度之和(根的深度為零)。上文的期望就是總深度的期望;當 時為 。
例題詳解
例題 1.9.4
(兩個鍵)
當 時,無論哪個鍵成為主元,都恰好與另一個鍵比較一次。公式給出 ,與直接計數一致。
例題 1.9.5
(三個鍵)
當 時,中位數以概率 首先被選中,此時進行兩次比較,之後不再有比較。端點以概率 首先被選中,此時進行兩次比較,隨後再對其餘兩個鍵進行一次比較。期望為 。公式給出 。
例題 1.9.6
(一對端點)
在五個已排序的鍵中,最小者與最大者只有在這兩者之一是全部五個鍵中第一個被選中的主元時才會被比較。它們被比較的概率為 。選到中間的主元則會立即把它們分開。
例題 1.9.7
(一次最壞情形的執行)
對於五個鍵,設在每個非平凡調用中都選中剩餘鍵中最小者。劃分比較次數為 。儘管其期望次數更小,這仍是該隨機化過程的一種可能執行。
常見錯誤
反例模式
期望並不意味著每次運行都如此
對三個鍵,先選端點會產生三次比較,而先選中位數則產生兩次比較。期望次數為 ,它既不是每次執行的上界,也不是任何一次實際執行的比較次數。
常見錯誤
(把比較指示變量當作互相獨立)
比較指示變量一般是互相依賴的。若某個內部主元將一對鍵分開,它同時也影響了其他哪些鍵對以後還能被比較。即使沒有任何獨立性假設,各期望之和仍然成立。
常見錯誤
(對輸入而非主元取平均)
期望是對算法的主元選擇而取,不是對輸入而取。若採用確定性規則,例如永遠以第一個鍵作主元,在已排序的輸入上會做 次比較,因為每個主元都是其子問題的最小元。界 對每個固定輸入都成立,正是因為只有主元是隨機的。
反例模式
相等的鍵會使精確公式失效
設鍵並不互不相同,且劃分規則把所有不大於主元的鍵放到左側。取 個相等的鍵。無論哪個鍵作主元,其餘兩個都與它比較並全部進入左側;規模為二的左側再花一次比較。每次執行都恰好做 次比較,而互不相同鍵的公式給出 。鍵對概率 不再適用,因為沒有任何鍵嚴格小於另一個。修正方式是假設鍵互不相同,或另行分析具體的相等處理規則;附加破平標識只有在比較確實使用這些標識時才有幫助。雙路與三路實作對重複鍵的處理各不相同,其精確比較次數需要另行分析。
為甚麼隨機優先級的觀點成立
對全部鍵作一個均勻隨機排列,可以看作給每個鍵分配一個唯一的優先級。任一非空集合中優先級最先的鍵,等可能地是該集合中的任一鍵。某個主元被確定後,其餘鍵的相對優先級順序仍然是均勻隨機的。把該順序限制到任一遞歸側,所得條件分佈與在該側重新作均勻主元選擇相同。
這種耦合是一種證明手段,並不要求實作真的生成完整的排列。它使我們即使在區間之外的主元更早被選出時,也能討論名次區間內的第一個主元。區間內優先級最先的成員在其成員中是均勻的,而在它出現之前,每個區間之外的主元都使該區間保持在一起。
精確計數依賴於這樣的規則:每個非主元鍵與其主元恰好比較一次。劃分的實作可能做額外的鍵比較,例如在執行某些邊界檢查時。它們仍可用類似的思想分析,但在未核對實際比較規則之前,不應原樣照搬所給的等式。
一個具體的四鍵計算
對四個鍵,名次相鄰的鍵對有三個。每一對必然被比較:沒有任何內部鍵能分隔相鄰名次,而該鍵對中第一個被選中的主元必是某個端點。名次區間長度為三的鍵對有兩個,各以概率 被比較;區間長度為四的鍵對有一個,以概率 被比較。求和得
調和數公式給出相同的數值,因為 ,且 。這一計算數的是鍵對事件,而不是獨立的擲硬幣。有些比較可以同時發生,而數值 不必是任何一次具體運行中的比較次數。
最不平衡的序列有多罕見?
對 ,取得最大比較次數的執行,在每個規模至少為二的子問題中都選取最小鍵或最大鍵。在規模為 的調用中,選到兩個極端之一的概率為 。在此前所有選擇都是極端的條件下,剩下的唯一非平凡調用的規模為 。把這些條件概率相乘得
當 時該概率為一;當 時為 ,與前面的直接例子一致。反之,非極端的主元會產生兩個非空的側,並使之後可能的最大比較次數低於僅剩一個子問題的情形。因此,對互不相同的鍵,在這一劃分規則下,所描述的事件恰好就是比較次數取最大值的事件。儘管其概率迅速減小,但對每個有限的 它都是可能發生的。
調和數估計的兩個方向
對 , 可這樣得到:對 ,把每個倒數 與 在 上的積分作比較。對於下界,把各項分成若干塊:從 到 的各項,每項至少為 ,共有 項。因此每個完整的塊至少貢獻二分之一。到 為止的完整塊的個數與 成正比地增長。
把這些界代入精確公式,即可解釋漸近增長。負的線性項不改變階:當 足夠大時,調和數因子超過某個固定正常數的量,像 一樣增長。對於小規模輸入,精確表達式的資訊更豐富,因為漸近記號會掩蓋相當大的差異。
鍵對的概率取決於名次與區間長度,而不取決於輸入最初的排列。在均勻選取主元與這一比較規則之下,由相同的互異鍵構成的每個固定排列,其期望次數都相同。這種對稱性是隨機化算法本身的性質,並不保證現實中的輸入是均勻隨機到達的。
總結
兩個鍵被比較,當且僅當其中之一是兩者名次之間(含端點)各鍵中最早的主元,這發生的概率為 。對鍵對指示變量求和,得到精確的期望及其 的增長階,而個別執行仍可能是二次方的。
練習
快速檢查
(計算名次 與 被比較的概率。)
解答 · 答案
它們的名次區間長度為三,所以概率為 。當名次 或名次 是名次 中第一個被選中的主元時,它們被比較。
快速檢查
(對四個鍵,在所述規則下,比較次數最多可能是多少?)
解答 · 答案
反覆選取極端鍵給出 次比較,而任何執行都不會超過這個數:第一次調用進行三次比較,並把其餘三個鍵分在兩側。若三個鍵全在同一側,之後至多再比較 次;若分成規模為二與一的兩側,至多再比較 次。因此總數至多為 。
快速檢查
(為甚麼兩個鍵至多被比較一次?)
解答 · 答案
比較發生在這對鍵中的一個被選為主元時。該主元不會出現在之後任何遞歸調用中,因此這一對鍵不會再次被比較。
快速檢查
(解釋為甚麼即使指示變量 可能互相依賴,期望的線性性仍然適用。)
解答 · 答案
對有限和,不論是否互相依賴,期望都對加法分配:。獨立性與某些乘積的計算有關,但在這裏並不需要。