隨機快速排序法

如果我們允許演算法使用隨機數產生器，那麼快速排序法會變得更有效率！

而引入隨機的方法很簡單：我們只要在快速排序法開始之前，隨機排列原本的輸入序列即可！

void RandomizedQuickSort(data_t *A, int n) {
  RandomPermute(A, n); // 隨機排列輸入的數值。
  QuickSort(A, n);     // 呼叫原本的快速排序法。
}

定理 13

假設 RandomPermute 可以均勻地產生隨機排列，那麼隨機快速排序法的期望時間複雜度為 \(O(n\log n)\)。

開始證明之前

大家還記不記得期望值的可加性呢？簡單來說，如果有兩個隨機變數（Random Variable） \(X, Y\)，那麼 \(X+Y\) 的期望值便滿足 \(\E[X+Y] = \E[X] + \E[Y]\)。我們把這個觀念應用在分析演算法的期望時間複雜度上面，可以把它想成：若這個演算法分成前後兩個步驟 \(A\) 和 \(B\)，兩個步驟的執行時間分別可以用隨機變數 \(T_A\) 與 \(T_B\) 表示。那麼整個演算法的執行時間就可以寫成 \(T_A+T_B\)，而這個隨機變數的期望值就可以利用期望值的可加性寫得 \(\E[T_A+T_B] = \E[T_A]+\E[T_B]\)。也就是說，我們只要分別分析兩個步驟的期望執行時間，加起來，就會等於整個演算法的期望時間複雜度了。

證明一：遞迴方法

我們定義 \(f(n)\) 為對 \(n\) 筆資料進行隨機快速排序的期望時間複雜度。我們想證明的是 \(f(n) = O(n\log n)\)。 首先，我們可以簡單地說明 \(f(n)\) 是非遞減的：多一筆資料，要排好序總得花更多力氣。 根據快速排序法的定義，我們選擇第一個數字作為 pivot，然後把整組資料拆成小於、等於、大於三個部分，再把小於 pivot、大於 pivot 這兩組資料分別遞迴下去排序。

由於一開始我們就把陣列中所有數字都打亂了，所以作為 pivot 的「第一個數字」其實是所有資料皆以均等的機率出現的。 因此，我們有 \(1/n\) 的機率選中最小值作為 pivot、有 \(1/n\) 的機率選中次小值作為 pivot、依此類推。

⚠️ 在這邊有一個小小的重點：遞迴時，資料已經被搬移過了。我們需要保證遞迴下去的時候，資料的分布仍然是「隨機」的：也就是說，對於該子問題，其資料排列在記憶體中任一順序機率均等。（證明可以使用條件機率或組合計數，這邊就略過啦）另一種繞過這個限制的方法，是修改隨機快速排序法，讓它每一次找 pivot 的當下，隨機選取一筆資料作為 pivot，分析起來是一樣的。

於是，利用期望值的可加性，我們可以得到關於期望時間複雜度 \(f(n)\) 的遞迴關係式：

\[ f(n) \le \begin{cases} O(1) & \text{ if } n \le 1,\\ \Theta(n) + \frac{1}{n} \sum_{p=1}^n (f(p-1) + f(n-p)) & \text{ otherwise.} \end{cases} \]

要怎麼證明這個遞迴式解出來會是 \(O(n\log n)\) 呢？最好用的證明工具當然就是數學歸納法囉！

數學歸納法

我們想要證明 \(f(n) = cn\log n\)，其中 \(c\) 是某個待定的常數。 假設選定 pivot 以後比較與分組所花費的時間為 \(\le c_0n\)，於是遞迴式會長這樣：

\[ \begin{aligned} f(n) &\le c_0 n + \frac{1}{n}\sum_{p=1}^n (f(p-1) + f(n-p))\\ &= c_0n + \frac{2}{n}\sum_{i=1}^{n-1} f(i) \end{aligned} \]

假設對於所有的 \(n' < n\)，都有 \(f(n') \le cn'\log n'\)。 我們想證明 \(f(n) \le cn\log n\)。而證明的關鍵，是利用後面總和的部分想辦法榨出一個 \(-c_0n\)，消去前面的項。

\[ \begin{aligned} f(n) &\le c_0n + \frac{2}{n}\sum_{i=1}^{n-1} f(i)\\ &= c_0n + \frac{2}{n}\left(\sum_{i=1}^{\floor{n/2}} f(i) + \sum_{i=\floor{n/2}+1}^{n-1} f(i)\right)\\ &\le c_0n + \frac{2}{n}\left(\sum_{i=1}^{\floor{n/2}} ci\log \frac{n}{2} + \sum_{i=\floor{n/2}+1}^{n-1} ci\log n\right)\\ &= c_0n + \frac{2}{n}\left(\sum_{i=1}^{\floor{n/2}} ci(\log n - 1) + \sum_{i=\floor{n/2}+1}^{n-1} ci\log n\right)\\ &= c_0n + \frac{2}{n}\left(\sum_{i=1}^{n-1} ci\log n - \sum_{i=1}^{\floor{n/2}} ci\right)\\ &= c_0n + c(n-1)\log n - c \frac{2}{n}\frac{\floor{n/2}(\floor{n/2}+1)}{2}\\ &\le c_0n + cn\log n - \frac{c}{4}n + (\frac{c}{4} - c\log n)\\ &\le c_0n + cn\log n - \frac{c}{4}n \\ &= cn\log n + (c_0 - \frac{c}{4})n \end{aligned} \]

如果我們選取 \(c \ge 4c_0\)，那麼便能使式子成立，從而命題得證。

數學歸納法是很繁瑣的，其他證明方法都不比數學歸納法來得繁瑣。為什麼呢？因為布吉納法索（被拖走）

下次我們來看看另外兩個利用期望值可加性和機率方法獲得的證明！