隨機快速排序法 2

今天我們來看看不使用遞迴方法，直接用機率方法分析隨機快速排序的另一個證明吧。 首先讓我們快速回顧一下定理 13。

定理 13

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

在證明開始之前

讓我們來回憶一下機率名詞。有一種隨機變數，其值只有 0 或 1，代表我們關心的事件出現與否。 而該變數值等於 1 的機率，自然地對應到事件出現的機率。 這樣的隨機變數被稱為指示隨機變數（Indicator random variable）。

大家一定還記得，快速排序法的時間複雜度（在一般的實作之下）與資料之間的「兩兩比較次數」呈現正比。 如果我們站在全局視角，關心「任兩個元素被拿來比較」的情形，在快速排序法會不會發生，那麼資料之間的兩兩比較總次數 $X$，便可以被拆成任兩筆特定資料被比較的次數 $X = \sum_{1\le i < j \le n} X_{ij}$，其中我們用 $X_{ij}$ 來表示排序完成後，應排在第 $i$ 位置的資料與第 $j$ 位置的資料的「是否在演算法執行期間被比較過」的指示隨機變數。

然後！我們就可以利用期望值的可加性，把所有隨機變數拆開來～輕鬆寫出快速排序法的期望時間複雜度：

$\E[X] = \sum_{1\le i < j \le n} \E[X_{ij}]\text{。}$

證明二：兩兩比較次數的期望值

這麼分析有個好處：我們可以分別計算出 $\E[X_{ij}]$ 的值。 比起追蹤整個演算法執行時 $n$ 個物件之間，直接將主力放在某兩個特定的資料上，分析起來可能簡單得多。 在分析開始之前，我們可以試想想看這個值可能會是多少？如果 $i=1, j=n$，那麼這兩個數字被直接拿來比較的機率其實相當低。 而這是因為，如果被選中的 pivot 在排序上介於 $i$ 與 $j$ 之間的話，顯然 $i$ 與 $j$ 會被分派到兩個不同的子問題下去遞迴，自此便無緣相見了。

此外，值得一提的是，在快速排序法進行中，如果有兩筆資料 $i$ 和 $j$ 被拿來比較，想必其中一者必定為 pivot。

有了以上的觀察以後，我們現在來說說要證明的敘述：

引理 14

對於所有的 $1\le i < j \le n$，都有 $\E[X_{ij}] = \frac{2}{j-i+1}$。

證明

我們可以偷偷對 $n$ 用數學歸納法來證明這件事情。

• Base Case: 當 $n=2$ 的時候，唯一有意義的 $i, j$ 是 $i=1, j=2$。顯然無論如何這兩筆資料都會比較到，因此 $\E[X_{12}] = 1 = \frac{2}{2-1+1}$ 滿足條件。
• Inductive Case: 當 $n>2$ 的時候，執行一步快速排序法，根據 pivot 的位置 $p$ 會產生三種情形：
  • pivot 剛好選中 $i$ 或 $j$（事件發生的機率為 $\frac{2}{n}$）：此時這兩筆資料必定會被比較到。即 $X_{ij}=1$。
  • pivot 滿足 $p\in [i+1, j-1]$（事件發生的機率為 $\frac{j-i-1}{n}$）：此時兩筆資料必定不會被比較。即 $X_{ij}=0$。
  • pivot 滿足 $p < i$ 或 $p > j$（事件發生的機率為 $1-\frac{j-i+1}{n}$）：此時 $i$ 和 $j$ 會不會被比較到，取決於遞迴呼叫的子問題。在此情形底下，無論子問題的規模有多大，$i$ 和 $j$ 總是被分到同一邊。假設這兩筆資料在子問題中的排序位置是 $i'$ 和 $j'$，顯然有 $j'-i' = j-i$。 根據歸納假設，此時這兩個數字被比較到的機率恰好等於 $\frac{2}{j'-i'+1} = \frac{2}{j-i+1}$。

於是乎，我們可將三種情形加起來，得到 $X_{ij}$ 的期望值：

$$\begin{aligned} \E[X_{ij}] &= \frac{2}{n}\cdot 1 + \frac{j-i-1}{n} \cdot 0 + \left( 1 - \frac{j-i+1}{n} \right) \cdot \frac{2}{j-i+1}\\ &= {\color{red}{\frac{2}{n}}} + \frac{2}{j-i+1} {\color{red}{- \frac{j-i+1}{n}\cdot \frac{2}{j-i+1} }} \\ &= \frac{2}{j-i+1} \end{aligned}$$

有了引理 14 以後，我們就可以開心地把所有的 $i, j$ 對應到的期望值加起來，也就得到了快速排序法的期望時間複雜度了！

$$\begin{aligned} \E[X] &= \sum_{1\le i < j \le n} \E[X_{ij}]\\ &= \sum_{1\le i < j \le n} \frac{2}{j-i+1}\\ &= \sum_{\ell=1}^{n-1}\sum_{i=1}^{n-\ell} \frac{2}{\ell+1} & & (\text{變數變換：} j = i+\ell ) \\ &= \sum_{\ell=1}^{n-1} \frac{2(n-\ell)}{\ell+1} \\ &\le 2n\left( \frac{1}{2}+\frac{1}{3} + \cdots + \frac{1}{n} \right)\\ &= O(n\log n) & & (\text{括弧部分是調和級數所以大約是} \ln n = O(\log n)) \\ \end{aligned}$$

說到底我們還是偷偷用了數學歸納法呀...明天我們來看第三種證明！ 保證（希望啦，如果沒想錯的話）沒有數學歸納法！

參考資料

• 關於機率論中，更嚴謹的 indicator function / indicator random variable 定義可以參考蔡宗翰的隨筆：https://ch-hsieh.blogspot.com/2012/07/indicator-function.html