almost 3 years ago

0 前言

在快速排序法的演算法中,假若我們要排序的數字是 。每一次的遞迴我們都會選擇其中一個數字 作為基準(英文稱為 pivot,不過中文翻譯成衛兵就覺得頓失趣味了),然後把所有數字當中,比 大的分在右邊、比 小的分在左邊,接著遞迴下去。

如果運氣比較背,我們就會得到一種很偏頗的分法,比方說,每一次我們都挑到了所有數字中最小或第二小的數字。

因此,如何準確地選擇 pivot,是一個趣味的課題。如果我們用允許使用隨機演算法,則期望的時間複雜度為 。在 1973 年的時候,由 Blum, Floyd, Pratt, Rivest 與 Tarjan 發表了一篇確定性(deterministic,即不包含任何隨機成分)的演算法,可以利用線性時間找出這一群數字的中位數。如此一來,就可以很平均地把數字分成兩邊。也就能達到理想的 時間複雜度了。

順道一提這五位作者當中,除了 Pratt(對,就是 KMP 演算法裡面的 P)以外,其他四位作者都得過資訊界最高榮譽的圖靈獎(Turing Award)。這個演算法除了被稱為 Medians of Medians 演算法以外,也被趣稱為 Five Guys Algorithm(米國好像有一家美式漢堡連鎖店叫做 Five Guys)。

1 作法

為了求得中位數,我們把題目擴大一些,目標是找出第 小(或第 大)的數字。

首先,我們先將所有數字每 5 個一組,然後找出每一組的中位數。如下圖所示:

接著我們把所有中位數蒐集起來,然後找出這些中位數的中位數 ,這個數字就被我們拿來當做 pivot。

然後利用這個 pivot,重新把所有數字分成小於 pivot 的、或是大於 pivot 的兩組。

重點來了!我們保證,至少有 個數字比 pivot 來得小(如淺紫色部分,每一組有 被算入,至少有一半的組被算入)、也至少有 個數字比 pivot 來得大(如深紫色部分)。
由於我們知道確實 pivot 的兩邊有多少數字,我們可以輕易地知道第 小的數字出現在哪一邊,然後遞迴下去。
由於每一次遞迴下去至多只會剩下原本數字個數的 ,時間複雜度可以列式為:

展開後解得 (當然我們如果用數學歸納法證明,會更直接而快速。)

2 QuickSelect

如同 QuickSort 一樣,我們也可以隨機挑選其中一個元素,並且視情況遞迴下去。因為不一定會選擇小塊或大塊的部分遞迴,所以我們以最差情形做考量(才會有 max)。期望的比較次數為:

利用數學歸納法,解得期望時間複雜度為 。當然在實作上這個方法相較確定性演算法也比較輕量一些。

3 STL

基本上如果我們想找出任何支援迭代器(Iterator)的容器 當中的第 小元素,可以直接使用 stl::nth_element() 這個函式。

http://en.cppreference.com/w/cpp/algorithm/nth_element

← 分而治之法(二):尋找極小值 分而治之法(四):D維支配點對問題 →
 
comments powered by Disqus