偏序集排序（六）

使用兩兩元素進行比較的排序演算法，不外乎就是採用「插入」或「合併」兩種策略。給定一個偏序集 \((P, <)\)，如同合併插入排序法一般，如果我們找到正確的插入順序，就可以得到一個只需要 \(O(\log n \cdot \log e(P))\) 次比較的偏序集排序方法囉！

找出最長可比鏈

在偏序集當中，一條鏈（chain）是指一個序列 \(x_1, x_2, \ldots, x_\ell \in P\)，而且他們形成一個全序關係：\(x_1 < x_2 < \cdots < x_\ell\)。我們可以利用動態規劃方法在 \(O(n^2)\) 的時間（或關於偏序集偏序關係總數之線性時間）內找出偏序集 \(P\) 中的最長鏈。

現在，我們將證明以下引理：

引理 27

令 \(\ell\) 為偏序集 \((P, <)\) 裡面的最長鏈的長度。那麼有 \(n-\ell \le \log e(P)\)。

證明

我們預計要證明的，其實是以下的式子：

\[ e(P) \ge 2^{n-\ell} \label{eq1}\tag{*} \]

換句話說，在最長鏈長度為 \(\ell\) 的條件下，我們想要證明任意偏序集裡面至少存在 \(2^{n-\ell}\) 個線性延伸。 要怎麼下手呢？我們其實也沒有太多招可以使用。一個簡單的方法便是使用數學歸納法。 這裡我們使用的數學歸納法，比較不太一樣：在固定總資料筆數 \(n\) 的情形下，我們要讓 \(\ell\) 的值從大到小進行歸納。

當 \(\ell = n\) 的時候，所有的資料都被排序完成了，此時 \(e(P) = 1 = 2^{0} = 2^{n-\ell}\)，滿足條件。

現在 \(\ell < n\)。根據歸納假設，對於任何偏序集 \(P'\)，只要它的最長鏈的長度是 \(\ell+1\)，那麼\(\eqref{eq1}\) 式成立。 考慮一個最長鏈長度恰好為 \(\ell\) 的偏序集 \(P\)，以及上面任何一條最長鏈 \(A\)。 首先，因為 \(\ell < n\)，因此對於任何鏈以外 \(P\setminus A\) 的資料 \(x\)，都至少存在 \(A\) 中某筆資料無法與其比較。 我們可以將 \(A\) 中的資料由小到大排列出來： \[ a_1 < a_2 < \cdots < a_\ell \]

因為 \(P\setminus A\neq \emptyset\)，存在一個最小的註標 \(i\)，使得存在 \(P\setminus A\) 中的某筆資料 \(x\)，與 \(a_i\) 不分軒輊。這件事情蘊含了 \(a_{i-1} < x\)。 我們如果拿 \(x\) 和 \(a_i\) 互相比較，根據比較結果，可能產生兩種情形：

\[ A_1: a_1 < \cdots < a_{i-1} < {\color{red}{x< a_i}} < a_{i+1} < \cdots < a_\ell \]

以及

\[ A_2: a_1 < \cdots < a_{i-1} < {\color{red}{a_i < x < a_{i+1}}} < \cdots < a_\ell \]

都是滿足偏序集 \(P\) 的偏序條件。令前者定義出來的新的偏序集為 \(P_1\)、後者為 \(P_2\)。 由於 \(x\) 是 \(P\setminus A\) 中的極小元素（對於所有 \(y\in P\setminus A\)、\(y\neq x\)，要嘛 \(x < y\) 要嘛 \(x\) 和 \(y\) 不可比），不難推得 \(e(P_1) \ge e(P_2)\)，而且 \(e(P) \ge e(P_1) + e(P_2) \ge 2e(P_2)\)。 現在，如果我們能證明 \(A_2\) 是 \(P_2\) 上面的一條最長鏈，由於它的長度為 \(\ell+1\)，套用歸納假設，我們可以知道 \(e(P)\) \(\ge 2e(P_2)\) \(\ge 2\cdot 2^{n-\ell-1}\) \(= 2^{n-\ell}\)，故 \(\eqref{eq1}\) 對 \(\ell\) 成立。

顯然 \(A_2\) 是 \(P_2\) 上面的一條最長鏈。為什麼呢？我們可以利用反正法證明之：反正一定會對。不是啦，我們可以利用反證法證明：假設存在一條更長的鏈 \(A'\)，其長度 \(|A'\vert \ge \ell + 2\)。 首先，這條鏈 \(A'\) 一定會包含 \(x\)，如果不會的話，那整條鏈早已出現在 \(P\) 中，與假設矛盾。

我們定義 \(I'_{< x}\) 為在 \(P'\) 裡面以 \(x\) 為最大元素的最長鏈。 類似地我們定義 \(I'_{> x}\) 為在 \(P'\) 裡面以 \(x\) 為最小元素的最長鏈。 考慮 \(I'_{< x}\) 裡頭到達 \(x\) 之前的那個元素，它可以是 \(a_i\)、也可以是其他元素。 如果是 \(a_i\) 接在前面的話顯然有 \(|I'_{< x}\vert \le i+1\)。如果是其他元素 \(y\) 接在前面的話，這個 \(y < x\) 關係顯然被包含在 \(P\) 之中、或是透過 \(y < a_i {\color{red}{< }}\ x\) 達成的，如果早已在 \(P\) 中，根據假設它只能是 \(a_1, \ldots, a_{i-1}\) 其中一者，此時 \(|I'_{< x}\vert \le i\)。 若是透過 \(a_i\) 達成的，那麼把 \(a_i\) 接上去會更長。 於是得到結論 \(|I'_{< x}\vert \le i+1\)。

類似地，考慮 \(I'_{> x}\) 裡頭緊接在 \(x\) 之後的那個元素，它可以是 \(a_{i+1}\)、或是其他元素 \(y'\)，無論是何種情形都可以得到 \(|I'_{> x}\vert \le \ell-i+1\)。於是有 \[\ell+2 \le \vert A'\vert = \vert I'_{< x}\vert + \vert I'_{> x}\vert - 1 \le (i+1) + (\ell-i+1)-1 = \ell+1\] 矛盾。

因此，不存在更長的鏈，於是原命題根據數學歸納法得證啦。

我們從引理 27，得出一個 \(O(\log n\cdot \log e(P))\) 次比較的偏序集排序演算法¹：

• 第一步：找出最長鏈 \(A\)。
• 第二步：對於剩下的所有資料，依序以二分法插入 \(A\) 中。

由於剩下的資料筆數至多為 \(\log e(P)\) 個，因此每一筆至多以 \(\log n\) 次比較就可以插入最長鏈中，整體比較次數是 \(O(\log n\cdot \log e(P))\) 次。整體計算時間為 \(O(n^2)\)（或偏序集大小）。

如果朋友們有餘力看到這邊，先容我致上深深的感謝。 相信大家看到這邊，應該會說：前一篇文章裡面提到的凸函數最佳化上哪去了？ 這東西會有用的。

我們明天將證明一個比引理 26 更強的定理：

\[ 4\log e(P) + nH(P) \ge n\log n \]

(在增加左手邊的係數變成 \(4\) 以後，不等式的右手邊就可以從 \(\log n!\) 變成 \(\log n^n\) 了。事實上這個係數可以是 \(2\)，不過證明比較複雜，所以我只會介紹係數等於 \(4\) 的版本。） 事實上，有了這個更強的定理以後，其實才能無痛證明引理 27 的 big-O 版本，昨天的引理 26 是不夠的。