動機
選擇算法要找的是某一個秩的元素,而不是把所有元素完全排好序。圍繞主元進行分割後,就能判斷目標秩落在哪一側,因此只需繼續處理這一側。如果每次選出的主元恰好都是剩餘元素中最小的,而目標是最大的,那麼剩餘列表每次只縮短一個元素,總工作量是二次的。若每次均勻隨機地選取主元,分析就不同了:平衡的主元出現得足夠頻繁,使得對每個固定輸入,期望總工作量都是線性的。
這個結果是對算法隨機選擇取期望的代價保證,而不是常數意義下的最壞情況執行時間。在下面的比較模型中,算法總能返回正確秩的元素;隨機性只影響工作量的大小。
定義
定義 1.11.1
(選擇問題與成本模型)
輸入由 個互不相同的全序元素和一個合法的秩 組成。對於大小為 的當前列表,在其元素中均勻地選取一個主元,所用的隨機選擇在給定當前列表的條件下是全新的。把其餘元素分割為比主元小的和比主元大的兩部分。若主元在當前列表中的秩等於 ,則返回該主元。否則,在唯一包含目標的一側繼續處理,並在丟棄較小元素和主元時相應調整目標的秩。
假設一次分割(包括選取主元)的代價至多為 個單位,其中 為固定常數;處理只含一個元素的列表的代價至多為 。在這個模型中,我們統計比較次數或其他單位操作。若主元在大小為 的列表中的秩介乎 與 之間(含兩端),則稱該主元是平衡的。
定理
定理 1.11.2
(正確性與終止性)
對於任意的主元選擇序列,隨機快速選擇都會終止並返回所要求的元素。
定理 1.11.3
(期望線性工作量)
對於由 個互不相同元素組成的每個固定輸入以及每個合法的目標秩,在算法隨機選擇上取期望的工作量至多為 的常數倍。
證明思路或證明
證明
(正確性與期望線性工作量)
分割之後,主元的秩等於比它小的元素個數加一。若目標秩等於該值,則主元即為所求。否則,目標位於相應的嚴格分割部分中,減去被丟棄的較小元素個數以及主元本身,即得它在該部分中的秩。這一不變量對每一種主元選擇都成立。遞歸繼續處理的列表比其父列表的元素更少,因此過程會終止,而且單元素的基本情形是正確的。
對於大小為 的列表,平衡秩的個數為
因此,均勻選取的主元以至少 的條件概率是平衡的。若主元平衡,則兩個嚴格分割部分的大小都至多為 :較小一側至多有 個元素,較大一側至多有 個元素。
把操作分成若干階段。一個階段從當前大小 開始,在第一個平衡主元出現時或算法終止時結束。由於大小只會減小,該階段內每次操作處理的元素都不超過 個。在還需要再進行一次操作的條件下,主元平衡的概率至少為 。因此,一個階段持續至少 次操作的概率至多為 ,其期望操作次數至多為 。於是它的期望工作量至多為 。
一個階段完成後,下一階段的起始大小至多是前一階段起始大小的四分之三。因此,無論後面的階段是否全部出現,它們的起始大小都以 為上界。把它們的期望工作量相加,得到至多
基本情形至多再貢獻一個常數 。這就證明了期望線性界。儘管所到達的列表依賴於先前的隨機選擇,條件概率的論證仍然有效。
證明透視
為甚麼可以對各階段求和
每個階段的起始大小都不超過某個確定的幾何級數上界。在給定其全部先前歷史的條件下,每個新的主元至少有二分之一的概率結束該階段。於是,由期望的線性性即可對各階段的代價求和,而無需假設各階段的大小互相獨立。
例題詳解
例題 1.11.4
(秩的更新)
設九個互不相同的元素被分割為四個較小元素、主元 和四個較大元素。主元的秩為五。要找秩為七的元素,就在較大的部分中遞歸地尋找秩為 的元素。主元不必就是答案,它所做的分割同樣是有用的。
例題 1.11.5
(平衡秩)
對於大小為八的列表,平衡秩從 到 ,八種可能中有五種。只要選中其中任何一個,每個嚴格分割部分至多有六個元素。一般的證明只需要較弱的概率界 以及上界 。
例題 1.11.6
(一個倒霉的序列)
在大小為 的列表上,設目標是最大元素,而每次選中的主元都是當前的最小元素。分割後的大小依次為 ,因此工作量可以是二次的。這個主元序列出現的概率為正,儘管該概率可能很小。
常見錯誤
反例模式
期望線性並不表示每次運行都是線性的
上述每次選最小元素為主元的序列是一次合法的執行,其工作量可以是二次的。線性的結論是對固定輸入在主元隨機性上取平均的工作量,而不是對每次執行都成立的上界。
常見錯誤
(要求主元必須是中位數)
平衡的主元不必是真正的中位數。它只需要使兩個可能保留下來的一側的大小都以一個常數比例為界;秩在 至 之間已經足夠。
常見錯誤
(把整個執行過程中主元的秩當作互相獨立)
階段論證依賴於在每一個當前列表上都成立的條件概率界;它並不假設整個執行過程中所有主元的秩是互相獨立的隨機變量。所到達的列表依賴於先前的選擇,但無論到達哪個列表,界 都成立。
常見錯誤
(忘記從秩中扣除較小的元素)
若主元有 個較小元素,而目標的秩滿足 ,新的秩是 ,而不是 。對九個元素、主元秩為五、 的情形,目標是四個較大元素中第二小的一個。在這四個元素中尋找秩 是沒有意義的。
反例模式
確定性的主元規則沒有期望線性的保證
有人會認為取列表第一項作主元與隨機主元同樣好。取已排序的列表 ,目標秩為 ,並永遠以第一項為主元。主元 的秩為一,因此保留列表 ,目標秩為 ,如此類推。各次分割的規模為 ,共做 次比較,而且每次運行都是如此,不只是運氣不好時才發生。線性界需要的是均勻的條件主元分佈,而不是任意一條規則。
追蹤目標的秩
正確性不變量針對的是目標元素,而不是主元是否能很好地估計其秩。設當前目標的秩為 ,而主元有 個比它小的元素。若 ,則在這些較小元素中尋找的恰好是同一個秩。若 ,則主元就是答案。若 ,則被丟棄的 個元素全都排在目標之前,所以目標在較大部分中的新秩為 。元素互不相同保證了每個元素恰好屬於三個區域之一,並且主元的秩是唯一的。
分割會重新排列輸入列表,但對於保留下來的任何一側,其內部並不要求有序。若對整個這一側排序,就會增加本分析沒有計入的工作量。算法在較小的列表上重複同樣的秩計算,直到找到目標。相比之下,排序算法通常需要處理兩側;這一差別說明了為甚麼它的遞推式可以有不同的增長速率。
例題 1.11.7
(四種可能的主元)
對於已排序的值 ,設目標是秩為二的元素。若主元為 ,則答案立即得到。主元為 時,保留 ,目標秩為一。主元為 時,保留 ,目標秩為二。主元為 時,保留 ,目標秩為二。這四個分支都是正確的;它們後續的代價可以不同。按照平衡的定義,對於大小為四的列表,秩一到三是平衡的。
使階段論證精確化
以任意一個在大小 處開始一個階段的歷史為條件。若算法在 個不平衡主元之後仍在運行,則其當前大小至多為 。要使該階段需要第 次操作,先前的每個主元都必須不平衡,並且沒有返回答案。在每一步,無論當前列表和目標秩如何,出現不平衡主元的條件概率至多為二分之一。把這些條件概率的上界相乘,得到概率至多為 。這是一條條件概率鏈;它並不斷言當前列表的大小是互相獨立的。
對於取非負整數值的隨機變量 ,把 寫成事件 的示性變量之和,即得尾和恆等式 。把它應用於階段長度,可得期望的分割操作至多為兩次。每次的代價至多為 ,因此以該階段起始歷史為條件,期望階段代價至多為 。算法可能在出現平衡主元之前就結束;這只會使階段變短。
對階段起始大小的幾何界在每一次執行中都是確定的。若某個階段以平衡主元結束且存在新的階段,則下一個列表不大於該主元所在列表的四分之三,而後者本身又不大於前一階段的起始列表。因此第 個階段的起始大小至多為 。對於從未出現的階段,視其代價為零。條件期望和確定性的大小界給出了上面的幾何級數求和,儘管階段的個數是隨機的。
期望代價與尾部陳述
期望並不直接說明每次運行的工作量都不超過 的某個小倍數。馬爾可夫(Markov)不等式確實給出了一個基本的尾部界。若總工作量 滿足 且 ,則 。例如,至多十分之一的運行其工作量至少為 。這個界是有效的,但可能比較鬆;更強的尾部陳述需要另行證明。
正確性與執行時間在這裏涉及不同的量詞。每個合法的主元序列都會返回正確答案,因為每一步都保持秩不變量並且嚴格縮短列表。期望時間定理對每個固定輸入都成立,但它是對算法的隨機選擇取平均。它不需要假設輸入的各種排列是等可能的。在隨機主元被抽取之前就固定輸入的對手,無法使均勻主元的條件計算失效。
當前主元必須均勻選取這一要求是實質性的。對已排序的列表只選第一個元素是確定性的做法,可能反覆選中最小的元素。只隨機選取一次下標,之後在分割後沿用某個確定性規則,未必能在後續每個列表上給出均勻的主元。證明要求在每次調用時都具有所述的條件分佈;具體實作必須論證其隨機化確實提供了這一點。
代價模型與邊界情況
在比較模型中,可以把在 中精確均勻地抽取一個整數視為基本操作。如果實作中只有公平的隨機位元,則可以抽取足夠多的位元來覆蓋一個二的冪次範圍,並拒絕落在所需範圍之外的值。這種拒絕法的期望抽取次數是有限的,但要給出細緻的位元代價界,就必須統計抽取次數及其長度。定理中關於選取主元與分割合計代價至多為 的假設,把這一模型選擇明確地寫了出來。
大小為一的列表是基本情形。此時無需選取主元,直接返回該元素。對於合法的非空列表,主元本身總是被丟棄或被返回,因此每一次遞歸繼續的列表都嚴格更小。證明排除了不合法的秩以及空輸入;具體實作在對列表取下標之前應檢查這些前提條件。
當存在相等的鍵時,必須謹慎地規定二路分割。一種常見的改法是形成小於、等於和大於三個區域,當所需的秩落在等於區域內時返回該鍵。其正確性和時間分析需要對重複鍵與隨機主元選取給出相應的處理。這裏的定理採用互不相同的元素,使得與主元相等就恰好確定一個元素,從而簡單的秩證明可以直接適用。
保證的比較
中位數的中位數選擇法通過花費工作量來選出具有可證明秩範圍的主元,從而給出確定性的最壞情況線性比較次數界。隨機快速選擇則通過對主元抽樣,並證明平衡階段平均而言很快出現,從而得到期望線性界。儘管兩者都避免了對整個輸入排序,但它們對某一次倒霉的執行所作的斷言是不同的。
在實踐中,主元選擇、記憶體移動、遞歸深度和比較代價都會影響效能。該定理在一個簡單的模型下孤立地考察了操作次數。它的價值恰恰在於其假設是明確可見的:條件均勻的主元、互不相同的鍵、線性的分割代價以及合法的秩。借用這個界之前,應當把另一種實作與這些假設逐一對照。
總結
分割保持目標的秩不變並縮短當前列表。均勻隨機的主元有常數的概率丟棄常數比例的元素,所以每個階段的期望工作量與該階段的起始大小成線性關係。在出現平衡主元之後,起始大小按幾何級數縮小,從而得到期望線性的總工作量。
練習
快速檢查
(若一個主元有四個比它小的元素,它的秩是多少?)
解答 · 答案
它的秩為五。
快速檢查
(對於大小為八的列表,按定義列出所有平衡秩。)
解答 · 答案
它們是 。
快速檢查
(為甚麼一次正確的執行仍然可能有二次的工作量?)
解答 · 答案
一個倒霉的序列可能使每次分割後保留的列表只縮短一個元素,從而得到二次的分割代價之和。
快速檢查
(期望界是對隨機輸入分佈取的平均嗎?)
解答 · 答案
不是。輸入是固定的;期望是對算法的主元選擇取的。