摘要訊息 : 某些問題的時間複雜度是有下界的.

0. 前言

對於任意問題, 設其至少有一個複雜度為 O(f(n)) 的演算法, 那麼稱 f(n) 是該問題複雜度的一個上界. 對於一個問題的複雜度上界 f(n), 要想其成立, 那麼只需要針對這個問題設計一個複雜度為 O(f(n)) 的演算法即可. 但是對於該問題, 若且唯若每一個可能的演算法的複雜度都為 \Omega (g(n)), 才可以說 g(n) 是該問題的複雜度下界. 這並不是一件容易的事情, 因為要證明對於該問題的任意演算法的複雜度至少在下界 g(n) 之上.

本文中我們將討論兩個比較問題的時間複雜度下界.

更新紀錄 :

• 2022 年 5 月 28 日進行第一次更新和修正;
• 2022 年 6 月 12 日進行第二次修正.

1. 最大最小問題

對於最大最小問題, 我們將要證明對於 n 個元素, 要想從中選出最大和最小元素, 至少需要進行 \left \lceil \frac {3n}{2} \right \rceil - 2 次比較. 至於是否存在重複的數據, 這不會影響最終的結果, 因為不論其數據是什麼, 總歸都需要進行比較. 但是為了不影響證明的一般性, 我們假設每個元素互不相同.

如果 n 個元素沒有順序可言, 那麼我們使用狀態向量 (a, b, c, d) 來描述最大最小問題的狀態. 其中, a = \mathop {\mathrm {card}}{A}, b = \mathop {\mathrm {card}}{B}, c = \mathop {\mathrm {card}}{C}, d = \mathop {\mathrm {card}}{D}, 集合 A 表示初始輸入集合, 集合 B 表示最大元素候選集合, 集合 C 表示最小元素候選集合, 集合 D 表示已經確定的非最大也非最小元素. 那麼初始狀態向量應該是 (n, 0, 0, 0). 由於我們需要篩選出最大的元素和最小的元素, 因此最終集合 A 中不再有元素, 集合 B 中有且只能有一個元素, 集合 C 中有且只能有一個元素, 集合 D 中應該有 n - 2 個元素. 那麼, 完成狀態向量就應該是 (0, 1, 1, n - 2). 在元素比較的過程中, 演算法會從一個狀態轉向另外一個狀態 :

• 當集合 A 中的兩個元素進行比較後, 較大的元素進入集合 B, 這是最大元素的候選; 較小的元素進入集合 C, 這是最小元素的候選. 除此之外, 不再有別的狀態轉變, 因此當集合 A 中的兩個元素比較後, 有狀態轉移 (a, b, c, d) \rightarrow (a - 2, b + 1, c + 1, d) 成立;
• 當集合 B 中的兩個元素進行比較後, 較小的元素會被放入集合 D 中. 這是因為那個被放入集合 D 的元素來源於集合 A, 經過比較後, 比這個元素小的元素放入集合 C 中. 那麼從所有元素的角度來說, 必定存在比這個元素小的元素, 然而由於集合 B 中又存在元素比它要大, 因此它既不是最大的元素也不是最小的元素. 因此有狀態轉移 (a, b, c, d) \rightarrow (a, b - 1, c, d + 1);
• 當集合 A 中的一個元素與集合 B 中的一個元素比較後, 存在兩種轉換狀態. 其中一種是集合 A 中的元素比集合 B 中的小. 此時, 集合 A 中這個元素被放入集合 B, 那個集合 B 中比較大的元素被放入集合 D. 則此時有 (a, b, c, d) \rightarrow (a - 1, b, c, d + 1). 集合 B 中有一個元素放入, 一個元素移除, 因此 \mathop {\mathrm {card}}{B} 不變. 另外一種是集合 A 中的元素比集合 B 中的元素小, 此時直接放入集合 C 作為最小元素候選, 那麼有狀態轉移 (a, b, c, d) \rightarrow (a - 1, b, c + 1, d);
• 當集合 A 中的元素和集合 C 中的一個元素進行比較之後, 同樣存在兩種狀態, 與上面這種情況相對應. 當集合 A 中的元素比集合 C 中的元素小的時候, 有 (a, b, c, d) \rightarrow (a - 1, b, c, d + 1); 當集合 A 中的元素比集合 C 中的元素大的時候, 有狀態轉移 (a, b, c, d) \rightarrow (a - 1, b + 1, c, d).

我們可以發現, 當 n 為偶數的時候, 要想從起始狀態 (n, 0, 0, 0) 向完成狀態 (0, 1, 1, n - 2) 轉變, 最快的途徑是集合 A 中進行 \frac {n}{2} 次比較. 此時, 全部元素都被放入集合 B 或者集合 C. 集合 B 和集合 C 中分別有 \frac {n}{2} 個元素. 要想從集合 B 中選出最大的元素, 兩兩進行比較, 至少要進行 \frac {n}{2} - 1 次比較. 同樣地, 對於集合 C 來說, 要想選出最小的元素, 至少要進行 \frac {n}{2} - 1 次比較. 完成之後, 將所有比較次數求和, 我們總共進行了 \frac {3n}{2} - 2 次比較. 當 n 為奇數的時候, 我們讓一個元素剩餘在集合 A 中不進行比較, 那麼就可以看作是偶數次數的情況. 集合 A 中的比較次數是 \left \lfloor \frac {n}{2} \right \rfloor. 要想選出最大或者最小的元素, 集合 B 和集合 C 分別都要進行 \left \lfloor \frac {n}{2} \right \rfloor - 1 次比較. 最後, 集合 A 中還剩下一個元素. 若這個元素是最大或者最少的元素, 那麼只需要再進行一次比較就夠了; 否則, 還要進行兩次比較. 因此, 當 n 為奇數的時候, 總共需要 \left \lceil \frac {3n}{2} \right \rceil - 2 次比較. 而當 n 為偶數的時候, \left \lceil \frac {3n}{2} \right \rceil - 2 = \frac {3n}{2} - 2. 因此, 對於任意最大最小問題的比較演算法, \left \lceil \frac {3n}{2} \right \rceil - 2 是比較演算法比較次數的下界.

2. 排序問題

對於任意 n 個元素, 其有 n! 種排列. 基於比較的排序演算法要做的實際上通過變換或者篩選, 從這 n! 種排列中選出標準排列. 對於 n 個元素 a_{1}, a_{2}, ..., a_{n} 中的任意兩個元素 a_{i} 和 a_{j}, 所有排列可以分為兩種情況. 當 a_{i} 位於 a_{j} 之前屬於一種情況, 還有一種是 a_{j} 位於 a_{i} 之前的情況. 其中, i, j = 1, 2, ..., n 且 i \neq j. 不失一般性, 我們再次假設所有元素互不相同. 當 a_{i} < a_{j} 時, 我們淘汰所有 a_{i} 位於 a_{j} 之後的所有排列. 此時, 還剩下 \frac {n!}{2} 種排列. 再比較一次之後, 剩餘排列的數量下降到 \frac {n!}{4}... 不斷重複, 最終只剩下一個排列的時候, 就是最終排序的結果. 不過不會有排序演算法這麼做, 這只是為了我們分析排序演算法下界的方法而已, 因為產生 n! 種排列的時間複雜度可能遠比排序演算法本身要高得多. 設 m 為需要比較的次數, 那麼當僅剩下一種排列的時候, 有 \frac {n!}{2^{m}} = 1 成立, 變幻後有 2^{m} = n!, 即 m = \log_{2} {n!}. 由於比較次數都是正整數, 因此有 m = \left \lceil \log_{2} {n!} \right \rceil. 亦即比較次數至少為 m = \left \lceil \log_{2}{n!} \right \rceil.

引理 1. n! \doteq \sqrt {2 \pi n}\left ( \frac {n}{e} \right )^{n}, 我們稱其為 Stirling 公式(Stirling's formula).

這個引理我們暫時不進行證明.

根據 Stirling 公式, 代入可知 \displaystyle {\begin {aligned} m &= \log_{2}{2 \pi n \left ( \frac {n}{e} \right )^{n}} \\ &= \log_{2} {\sqrt {2 \pi n}} + \log_{2} {\left ( \frac {n}{e} \right )^{n}} \\ &= \frac {1}{2} \log_{2}{2 \pi n} + n \log_{2}{\frac {n}{e}} \\ &= \frac {1}{2} \log_{2}{2 \pi n} + n\log_{2}{n} - n\log_{2}{e} \\ &= \Omega(n\log {n}). \end {aligned}} 因此, 每一個基於比較的排序演算法在最壞情況下都要進行 \Omega(n \log {n}) 次比較.

設要排序的集合為 \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} \right \}, 我們也可以將比較的過程畫成一棵二元樹 (《【資料結構】二元樹》) :

由於 n 個元素總共有 n! 種排列, 所以 Figure 1 中的比較樹最重從根節點到葉節點的路徑總共也會有 n! 條. 根據二元樹的高度性質, 這棵二元樹的高度應該是 \left \lceil \log_{2}{n!} \right \rceil. 從這個角度, 同樣也可以說明每一個基於比較的排序演算法在最壞情況下都要進行 \Omega(n\log {n}) 次比較.

綜上所述, 基於比較的排序演算法的時間複雜度至少為 \Omega(n\log {n}).