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

在本篇文章中, 我們主要針對使用比較的演算法進行複雜度下界的論述

1. 最大最小問題

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

為了證明, 我要引入一種全新的方法 : 狀態空間方法. 這是一種對演算法進行抽象分析的方法, 由於其抽象性, 所以並不適合描述一個演算法, 只能用於分析. 這種方法首先要描述一個演算法的起始狀態、中間狀態和完成狀態, 還要有從一個狀態向另一個狀態轉變的方式, 最終確定從起始狀態到完成狀態所需要的最少轉換次數. 這個最少的轉換次數, 就是一個問題的複雜度下界

我們使用一個狀態向量來描述演算法的狀態 : (a, b, c, d), 其中 a = cardA, b = cardB, c = cardC, d = cardD. 集合 A 表示初始輸入集合, 集合 B 表示最大元素候選集合, 集合 C 表示最小元素候選集合, 集合 D 表示已經確定的非最大也非最小元素. 那麼在演算法剛剛開始的時候, 所有 n 个元素处于集合 A 中等待比较, 那么初始状态就是 (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 中有一個元素放入, 一個元素移除, 因此 cardB 不變. 另外一種是集合 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

引理 (斯特靈公式(Stirling's formula)) : n! \doteq \sqrt {2 \pi n}(\frac {n}{e})^{n}

這個公式我們暫時不進行證明. 根據斯特靈公式, 代入可知

\begin {aligned} m &= \log_{2}{2 \pi n (\frac {n}{e})^{n}} \\ \\ &= \log_{2} {\sqrt {2 \pi n}} + \log_{2} {(\frac {n}{e})^{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}) 次比較

除了上面這種證明方法, 還可以使用決策樹進行證明, 由於樹我們還沒有講, 所以暫時不涉及