Processing math: 100%

隨機快速排序法 2

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

定理 13

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

在證明開始之前

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

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

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

\E[X]=1i<jn\E[Xij]

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

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

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

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

引理 14

對於所有的 1i<jn,都有 \E[Xij]=2ji+1

證明

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

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

於是乎,我們可將三種情形加起來,得到 Xij 的期望值:

\E[Xij]=2n1+ji1n0+(1ji+1n)2ji+1=2n+2ji+1ji+1n2ji+1=2ji+1

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

\E[X]=1i<jn\E[Xij]=1i<jn2ji+1=n1=1ni=12+1(變數變換:j=i+)=n1=12(n)+12n(12+13++1n)=O(nlogn)(括弧部分是調和級數所以大約是lnn=O(logn))


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

參考資料

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