隨機快速排序法 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