動機
選出第 小的元素並不需要對全部元素排序。圍繞主元進行劃分後,我們就知道所求的秩位於哪一側,因此只需在這一側繼續查找。不幸的主元仍會令普通的快速選擇(quickselect)耗費二次時間。中位數的中位數方法額外花費一些工作來選取主元,使得每一次足夠大的遞歸調用都能丟棄輸入中固定比例的元素。
我們在比較模型中,對互異元素證明最壞情況上界。證明中的常數是有意取得寬鬆的;關鍵在於兩個遞歸子問題的規模之和比原規模小一個線性量。
定義
定義 1.10.1
(秩選擇與下中位數)
輸入是 個互異的全序元素組成的列表,以及秩 ,其中 。秩為 的元素是列表中恰有 個比它小的元素的那一個。 個互異元素的下中位數,是其中秩為 的元素。
當 時,直接對列表排序並返回第 個元素。當 較大時,將列表分成每組五個元素的若干組,最後一組可能不足五個。對每組排序並保留其下中位數。然後遞歸地選出這 個組中位數的下中位數 。
將原列表劃分為小於 的元素、主元 ,以及大於 的元素。若 等於較小部分的大小加一,則返回 。否則,在相應的部分上遞歸,並在丟棄較小部分與主元之後相應調整 。元素互異令這三個部分沒有歧義;若要處理重複元素,則需要另行進行等鍵劃分並檢查秩。
定理
定理 1.10.2
(主元丟棄界)
對於 ,原列表中至少有 個元素不小於主元,且至少有 個元素不大於主元。因此,兩個嚴格劃分部分的大小都至多為 。
定理 1.10.3
(正確性與線性最壞情況工作量)
該算法返回秩為 的元素。在固定大小的分組排序和線性時間劃分的前提下,其最壞情況比較次數為 。
證明思路或證明
證明
(計算主元兩側的元素)
至少有 個組中位數不小於這個作為主元的中位數(計入主元本身),也至少有 個不大於它。至多有一組是不完整的。每個中位數不小於 的完整組都至少含有三個不小於 的元素;這些組兩兩不相交。因此至少有 個元素不小於 。對另一側應用同樣的論證,即得較小一側的界。這一計數包含了主元本身,這已經足夠:嚴格較小的部分排除了所有不小於 的元素,嚴格較大的部分同理。
證明
(正確性與線性遞推式)
關於正確性:劃分給出主元在當前列表中的準確秩。若目標秩等於該秩,則主元即為答案。否則,被丟棄一側的所有元素與主元都已知位於目標的同一側。在剩餘列表上以相應的秩遞歸,所求元素得以保留。子問題的規模不斷縮小,而固定大小的基礎情形由排序正確處理,因此對列表大小作歸納即證明了正確性。
對每組排序只需常數工作量,因為組的大小至多為五;共有 個組,而劃分的代價為 。設 為所有大小至多為 的合法輸入上的最壞比較次數,因此它是非遞減的。於是對某個常數 以及 ,
第一次遞歸調用用於選取主元,第二項則是所探索的那個劃分部分的上界。對於歸納界 ,兩個遞歸規模之和至多為 。當 時,;取 ,並使其足夠大以涵蓋有限多個基礎規模。則 。歸納法證明了 。
證明透視
兩次遞歸調用,卻只有一次劃分
遞推式的每一項各有來源。 是從各組中位數中選取主元的那次調用; 是其後所探索的唯一一個劃分部分,並非兩個部分都探索,因為目標至多位於一側。分組大小五給出比例 ,主元丟棄界給出 。兩者之和為 ,這個約為 的十分之一的缺口,正是用來支付線性工作量 以及 時的附加項 。關鍵的一步是對兩個規模同時使用歸納假設,得到 。
去掉任何一個成分,論證都會失效。若改為每組三個元素,兩個比例約為 與 ,和約為 ,沒有缺口來吸收 。因此證明依賴的是這兩個具體的比例,而不只是存在兩次較小的調用。
例題詳解
例題 1.10.4
(秩的更新)
假設對九個互異元素進行劃分,主元 之下有四個元素,之上也有四個元素。主元的秩為五。要選取秩為七的元素,丟棄四個較小的元素和 ;所求元素在四個較大元素中的秩為 。
例題 1.10.5
(組中位數證書)
對於已排序的一組 ,其中位數為 。若主元至多為 ,則該組中的 這三個元素不小於主元。若主元至少為 ,則 這三個元素不大於主元。證明中正是對不相交的完整組累計這一局部事實。
例題 1.10.6
(為甚麼端點主元有風險)
若快速選擇始終選取最小元素作為主元,而所求的是最大元素,則每一步只丟棄一個元素。劃分工作量之和為 。中位數的中位數方法的界排除了大規模調用中這種持續的失衡。
常見錯誤
反例模式
選取中位數的中位數不等於選取真正的中位數
一個誘人的說法是:主元就是整個列表的中位數。取 ,分成 、 和 三組。各組中位數為 ,所以中位數的中位數是 ,而這十五個數的真正中位數則是 。按所述實作,這個小列表會走基礎情形;這裏的例子只是單獨展示主元的構造。因此證明並不假設主元恰好處於正中間的秩,只要求較弱的保證:主元在兩側都至少留下 個元素。
常見錯誤
(計入不完整的組)
不完整的組在其中位數的某一側可能含有不足三個元素,因此在必要時必須將其排除在每組三個元素的計數之外。這正是界中要減去一組的原因:得到 ,而不是 。
常見錯誤
(害怕兩次遞歸調用)
含有兩次遞歸調用的遞推式並不會自動導致超線性。這裏兩次調用的規模之和至多為 ,留有餘地來吸收線性工作量。只有當規模之和達到 時,論證才會失效。
秩的界從何而來
證明計數的是組,而不是尋找主元時實際進行的單次比較。列表被分成互不相交的組,因此某一組中被證實的三個元素不可能同時被算作另一組的元素。當某個完整組的中位數不小於 時,該中位數及其之上的兩個元素都不小於 。當其中位數不大於 時,該中位數及其之下的兩個元素都不大於 。我們分別對兩側計數;像主元這樣的元素可以同時計入兩個非嚴格計數,這無妨,因為每個計數所界定的是不同的嚴格劃分部分。
共有 個中位數,其中包括可能存在的不足額末組的代表。即使 為偶數,這些代表的下中位數也滿足:至少一半的代表不大於它,至少一半不小於它。每一側被證實的組中至多有一個是不足額的,因此減去一個完整組即得安全的下界。這一估計犧牲了一些本來有效的元素,但線性時間的證明只需要常數比例,而不需要最佳的加性常數。
主元本身是原有元素之一。在實作中,找到它之後可以將其移動或複製到單獨的變量中,但劃分時仍須將它恰好計入一次。若有 個元素嚴格較小,則主元的秩為 。當 時,丟棄這 個較小元素和主元,在較大部分中的目標秩為 。由於 ,這個新的秩落在較大部分之內。當 時,原來的秩在較小部分中本就有效。
遞推式為何閉合
選取主元的那次調用至多處理 個元素。被選中的劃分部分至多含有 個元素。因此二者之和至多為 。其中的加性常數四並未被忽略:當 時,所節省的十分之一的 比它至少多出 。再取一個足夠大的歸納常數,以支付線性的非遞歸工作量,估計便得以閉合。有限多個較小的輸入則透過增大同一個常數來涵蓋。
證明將 定義為大小至多為 的輸入上的最壞代價,使其成為非遞減函數。這樣,規模未知的遞歸調用就可以用 在規模上界處的取值來界定。若 僅對恰好 個元素的輸入定義,則單調性需要另行論證。定義這個單調包絡使不等式一目了然,並且對任何具體輸入都不會削弱最終的上界。
該遞推式是最壞情況下的不等式,而非精確的等式。主元可能立即返回,被選中的劃分部分可能小於上界,各組的排序也可能用到更少的比較。為了得到上界,我們為每次調用的分組、排序與劃分各計入固定的線性工作量。證明並不聲稱每次執行都恰好用 次比較,也不聲稱這些常數能與實際中的隨機化選擇算法相競爭。
比較模型與下界
定理統計的是元素之間的比較次數,並把移動或索引元素視為常數工作量。固定大小的基礎情形可以使用任何正確的排序方法;由於它處理的元素少於一百個,其最壞代價被一個絕對常數所界定。若比較本身代價高昂,則每次比較的代價必須另行計入。記憶體使用和數據移動同樣是獨立的資源:本證明是在所述模型下關於比較次數與線性工作量的上界。
求最大值說明了為何線性工作量是自然的目標。在比較模型中,除最大值之外的每個元素至少要輸掉一次比較;否則,一個從未輸過的元素在與已觀察到的結果相容的某個全序下仍可能是最大值。每次比較至多產生一個輸家,因此最壞情況下至少需要 次比較。所以,選擇算法的 界對於求最大值這一實例而言是漸近最優的。這個論證並不需要對整個列表排序。
重複鍵與模型邊界
元素互異的假設令主元可以獨立成一部分。若存在重複鍵,正確的改寫應將列表劃分為小於、等於和大於三個區域。若所求的秩落在等於區域之內,則返回該公共鍵;否則在某一嚴格側上以調整後的秩遞歸。完整的證明必須修改計數與劃分的論證,以顧及相等的元素。本單元陳述的是互異元素的定理,而不是悄悄依賴一種可能反覆保留大量相等鍵的二路劃分。
反例模式
重複鍵會令互異元素算法失效
一個誘人的說法是:鍵重複時算法無須修改仍然成立。取 個相同的鍵,。主元 就是這個鍵,因此沒有元素嚴格小於或嚴格大於它:兩個嚴格部分都是空的,秩 不等於 ,也沒有可供遞歸的部分。三路劃分的修正辦法,是把列表分成小於、等於和大於三個區域,並在秩落在等於區域之內時返回該公共鍵。
固定的五元素分組對算術也很關鍵。把五換成其他大小,會同時改變選取主元那次調用的規模和所保證的丟棄比例。不重新計算這些量,就不能照搬不等式 。一般的策略比這個特定選擇更為寬廣,但具體的證明屬於所述的分組與代價模型。
總結
秩受到控制的主元使得一次劃分中的一側可以被丟棄。按五個一組分組給出了固定比例的保證,而遞歸地選取主元則需要再花費一次規模更小的調用。這兩個規模上界加上線性的劃分工作量,得出線性的最壞情況比較次數。
練習
快速檢查
(某主元之下有七個元素。它的秩是多少?)
別忘了主元本身。
解答 · 答案
它的秩是八:有七個較小的元素排在它前面。
快速檢查
(若所求的秩為十,而主元的秩為八,則在較大的元素中要找的是第幾名?)
數一數被丟棄的元素有多少個。
解答 · 答案
目標是比主元大的元素中第二小的一個,因為包括主元在內的八個元素已被丟棄。
快速檢查
(為甚麼至多只有一組不完整?)
想想列表是怎樣被切成各組的。
解答 · 答案
把列表按順序每五個分成一組;只有最後一組可能不足五個元素。
快速檢查
(為甚麼對每組排序仍然只是線性工作量?)
同時計算每組的成本和組數。
解答 · 答案
每組至多有五個元素,所以排序一組只需固定次數的比較;組數為 。