比較排序下界

到目前為止我們看過的排序方法，都是只要支援「能夠兩兩互相比較」，就可以由小到大排好序的演算法。其中幾個排序演算法如：合併排序法、隨機排序法、堆積排序法等等，都能夠達到 \(O(n\log n)\) 的時間複雜度，幾乎線性。但終究還是與顯然下界（至少要看過所有輸入的資料才能排序，因此任何能夠將資料正確排序的演算法都必須花費 \(\Omega(n)\) 的時間）有著隔閡。下面這個定理告訴我們，如果只計算比較次數的話，我們能得到更大的下界。

定理 18

任何一個確定性演算法，如果存取輸入資料時僅能夠進行「兩兩互相比較」。那麼排序 \(n\) 筆資料，最壞情形下至少要進行 \(\ceil{\log n!} = \Omega(n\log n)\) 次比較。

證明

對於輸入的 \(n\) 筆資料，排序完畢後的輸出，相對於輸入總是一個排列（Permutation）。由於 \(n\) 筆資料總共有 \(n!\) 種不同的排列情形，每問一個問題「是否 \(A[i] > A[j]\)？」，我們可以把仍滿足先前所有提問的排列找出來，形成集合 \(\mathcal{S}\)，然後分成兩組：滿足當前這個問題（\(A[i] > A[j]\)）的所有排列 \(\mathcal{S}_{yes}\)、或者是不滿足當前問題（\(A[i] \le A[j]\)）的所有排列 \(\mathcal{S}_{no}\)。這兩個排列集合是不相交的，換句話說，如果我是邪惡的餵輸入的人，我可以設計一組輸入，讓滿足所有到目前為止的排列們，恰好就是 \(|\mathcal{S}_{yes}\vert \) 或 \(|\mathcal{S}_{no}\vert \) 之間比較大的那一個。換句話說，在運氣最好的情況下，你的演算法也只能夠剔除一半的排列數。

為了讓演算法完全正確，任何確定性的演算法，在 \(|\mathcal{S}\vert > 1\) 的任何時刻，演算法都不能輸出答案。否則的話，總是存在另兩種不同的輸入（\(1\) 到 \(n\) 的排列），經歷過一連串比較得到一模一樣的答案以後，演算法就停下來而且輸出了其中一個作為答案。此時，另一個輸入再餵進同樣的演算法，就會錯掉了。至少要經過幾次比較，才能讓滿足條件的排列集合 \(\mathcal{S}\) 變成唯一的排列呢？由於每一個問題只能讓排列數降低成一半，至少得經過 \(\ceil{\log n!}\) 次比較才行。

於是我們就得到 \(\Omega(n\log n)\) 的比較排序下界啦！

這個證明是少數幾個能夠簡單推論出的非顯然下界，我們應該要多多珍惜。一般來說，要證明時間複雜度下界，通常可以從資訊理論（Information Theory）的角度，加上決策樹來下手。

我們可以把這套方法，應用在其他類似的問題中。比方說，假設我們有兩個已經排好序的數列 \(A[1..n]\)、以及 \(B[1..m]\)。合併排序法的「合併」步驟，需要花費 \(O(n+m)\) 次比較。這個方法是最優的嗎？我們可以透過類似的分析，得到有趣的結論：

演算法的分析與證明

比較排序下界

定理 18

證明

定理 19

證明

這個證明告訴我們什麼？

推薦閱讀