兩個不同的動詞：演算法很「快」，問題很「難」
你至今做過的每一次分析都長著同一副模樣。你手裡握著一個特定的演算法——比方說合併排序——你數出它的工作量，然後報出一個像 O(n log n) 這樣的大O界。那句話是對單一一個演算法的承諾：這個方法所做的事，從不超過大約 n log n 次比較。它對「某個更聰明的方法能不能做得更好」隻字未提。上界是關於某一位攀登者爬到了某個高度的主張。
下界把問題反轉過來，而且反轉得很徹底。它無關任何單一演算法。它是對問題本身的主張，範圍涵蓋每一個可能被寫出來的演算法，包括尚無人發明的那些。「用比較把 n 個項目排序，在最壞情況下至少需要大約 n log n 次比較」並不是說我們的排序需要這麼多——而是說沒有任何比較排序能避開它，永遠不能，無論多麼天才。上界是靠展示出一個方法來建立的；下界卻必須一口氣排除掉一整片無窮的方法之海。這正是動詞改變的原因：演算法有快有慢，但一個問題有易有難，而要證明「難」是深奧得多的一件事。
為何沒有模型，下界就毫無意義
下界之所以微妙，關鍵在這個陷阱，而且它值得你在其他一切之前先內化。你無法證明每一個可想像的演算法都需要某個工作量，除非你先精確說出一個演算法被允許做哪些事。如果某台機器能在一個神奇的步驟裡問「這個串列已經排好了嗎？」，那排序就只要一步，n log n 的主張就會是錯的。這個界唯有在我們固定了遊戲規則之後才成立——也就是那個說明「哪些操作算數、它們各花多少」的計算模型。
對排序與搜尋而言，自然的規則是比較模型：演算法可以比較兩個元素、但只能得知它們的相對順序（小於、等於、大於），而我們就數這些比較。它不能窺看某個元素真正的數值、不能對它做雜湊、也不能把它當作陣列索引——它只能問「這兩個誰比較大？」。對於一個必須在任何你能排序的東西上運作的演算法而言，這條規則是誠實的——字串、紀錄、帶有比較函數的自訂物件——它對那些東西的內部位元一無所知。著名的 Omega(n log n) 排序下界，是一個關於這個模型的陳述，而下一篇會把使它可被證明的精確機器——決策樹——建立起來。
模型不是作弊，也不是弱點——它正是讓這個界長出牙齒的東西，也正是為什麼同一個問題在不同模型裡能有不同的下界。比較排序就是 Omega(n log n)，沒得商量。但如果你的鍵恰好是某個小範圍內的整數，你就被允許運用它們的數值當索引，於是計數排序或基數排序能在 O(n) 內跑完——它們之所以能逃出 n log n 屏障，正是因為它們踏出了比較模型之外。這裡沒有矛盾：那個下界從頭到尾只談論遵守比較規則的演算法。讀任何一個下界時，都要連同它的模型一起讀，就像你讀速限時要連同它的路牌一起讀。
這一階你將掙得的四件工具
你究竟要怎麼證明某模型裡的所有演算法都需要某個工作量？這有少數幾個反覆出現的技巧，這一階其餘部分各給一篇。第一件是決策樹模型：把任何比較演算法想成一棵樹，每個內部節點是一次比較、每條分支是一個結果。輸入所走的那條路徑就是該演算法的一次執行；最壞情況的比較次數，就是這棵樹的高度。於是這個界化成了關於樹的事實：一棵必須區分 L 種不同結果的二元樹，高度至少要 log2(L)。
那條關於樹的事實，驅動了第二件工具——資訊論論證，這是這裡最深刻的想法，值得用白話講清楚。每次比較只回傳少數幾種答案之一，因此它至多揭露固定份量的資訊——若答案是是／否，就至多一個位元。與此同時，問題本身有許多必須被分辨開來的可能答案：把 n 個相異項目排序，必須從 n 階乘種可能排列中挑出正確的那一個。若每次比較至多攜帶一個位元，你就至少需要 log2(n 階乘) 次比較才能蒐集到足夠的位元，而 log2(n 階乘) 約為 n log n。一句口號：你能區分的情況數，不可能多過你的提問所能攜帶、用以分隔它們的資訊量。這是一個計數論證，不是一個比聰明的論證——也正因如此，它能一口氣綁住每一個演算法。
第三件工具——對手論證——更具戰鬥性，也美妙地具體。想像你不是在解決問題，而是在對抗那個演算法：你扮演輸入的角色，只要從不與你先前給過的答案相矛盾，你就能臨機決定每個元素的數值。你的目標是盡可能久地讓演算法蒙在鼓裡，逼它問更多問題。如果你總能撐到它問完 k 個問題，那麼每一個演算法都至少需要 k 個——因為你構造出的那個惡意輸入打敗了它們全部。我們會用它來證明「找最大值」與「同時找最大與最小」的緊界，以及「中位數」的下界（並非緊界）。第四件工具——歸約——是一根槓桿：如果你能廉價地把一個已知很難的問題轉化成問題 B，那麼 B 至少必須一樣難，因為一個容易的 B 也會讓那個難的問題變容易。
一個你三行就能證完的小小下界
抽象的東西，在你能完整握住的一個誠實範例之後會落地得更好，所以我們一起來證這個：在比較模型中，找出 n 個相異數的最大值，至少需要 n-1 次比較。直到現在你都樂呵呵地寫一個單趟掃描的求最大值迴圈、稱它為 O(n)；而這個下界證明了 O(n)——其實正好是 n-1——是任何比較方法所能做到的最好水準。這個論證是顆小寶石，因為它完全不依賴演算法是怎麼寫的。
- 把它框成一場錦標賽。一個數一旦輸掉哪怕一次比較（被發現比某個東西小），就稱它為「輸家」。最大值從不輸掉任何比較；其餘每個元素都至少必須輸一次，否則我們無從確定它不是最大值。
- 非最大值的元素有 n-1 個，每一個都需要成為輸家。一次比較恰好產生一個新的輸家（兩者中較小的那個——而若其中一方原本就已是輸家，那這次比較根本不產生任何「新」輸家）。
- 因此，要製造出 n-1 個相異的輸家，你至少需要 n-1 次比較。沒有任何比較演算法能用更少次數收工，所以下界是 Omega(n)——而既然那個顯而易見的迴圈以 n-1 與之相符，這個界就是緊的。
再讀一次第 2 步，因為它才是真正在幹活的那一步，而且它偷偷就是一個喬裝過的對手。「每次比較至多製造一個新輸家」這句話是一份預算：朝向確定性的進展，被配給成每個提問一單位，而你需要 n-1 單位的進展。多數下界，骨子裡都正是這個樣子——一個必須達到某目標的量，搭配一個證明：模型的每一步只能讓它移動有界的幅度。資訊論工具與對手工具，不過是運行這同一套記帳的兩種系統化方式罷了。
下界承諾了什麼——以及沒有承諾什麼
請對這個主張說得精確，因為它很容易被讀過頭或讀不足。一個 Omega(n log n) 的界，是關於某模型內漸進的最壞情況成長的陳述。它並非說每個輸入都慢——一個近乎排好的輸入可能很快就跑完——它說的是最壞的那個輸入會逼出那麼多工作。而且如同每一個漸進主張，它隱藏了常數、且只管轄大的 n：一個 Omega(n log n) 的方法仍然只有過了某個交叉規模之後才贏過 O(n^2) 的方法，對極小的 n，那個「較慢」的方法反而可能勝出。下界告訴你的是關於擴展性與不可避免性的事，而非關於「在你那串 20 個元素的串列上哪個方法最快」。
同樣關鍵的是：下界與它的模型黏在一起，而這個界只在模型誠實的程度上才那麼強。Omega(n log n) 排序對比較演算法是滴水不漏的；它對計數排序隻字未提，因為計數排序根本不玩那場遊戲。這種模型相對性不是瑕疵——正是它讓一個下界得以成為一條真正的定理、而非一個猜測。與這個領域最著名的未決問題對照起來，反差很尖銳：對於那些NP完全問題，我們並沒有可相提並論的下界。「NP完全」意味著目前不知道有多項式時間演算法，但沒有人證明過不存在——在那裡證出一個超多項式下界，本質上就是那個P 對 NP 問題，著名地仍然未決。這一階裡那些決策樹下界之所以珍貴，恰恰是因為它們屬於我們能夠無條件證明的少數下界之一。