為何非得要一個模型不可
上一篇劃下一條清楚的界線：下界是對「問題」的主張，而不是對某一支程式的主張。它說的是：每一個正確的演算法都至少得付出這麼多。可是「每一個」這個詞是個陷阱。演算法有無窮多種——巧妙的、醜陋的、甚至還沒被發明出來的。你怎麼可能一次推理全部？做不到，除非你先把「對這個任務而言，什麼才算是一個演算法」講死。這份講死了的描述，就叫做計算模型，而選定一個模型，是任何下界證明誠實的第一步。
對排序與搜尋而言，自然的模型是比較模型。在這個模型裡，演算法只被允許透過比較兩個元素、問「a 是否小於 b？」來認識它的輸入。它可以比較、依答案分支、搬動資料、記住任何它想記的東西——但通往真實數值的唯一窗口，就是比較得到的是／否結果。合併排序、快速排序、堆積排序、插入排序、二分搜尋：它們全都活在 比較模型之中。除了透過比較，它們從不偷看一個數字的位元。
把演算法畫成一棵樹
美妙的一步在這裡。一旦演算法只能問比較問題，它的整個行為就坍縮成一棵問題之樹。每個內部節點是一次比較——「a_i < a_j？」——帶有兩個子節點，一個對應「是」，一個對應「否」。演算法從根開始，問該處的比較，依答案往左或往右走，在落腳的節點問下一個問題，如此繼續。它不執行任何其他會影響路徑的步驟。當它終於停下，它已抵達一片葉子，而葉子上承載著演算法所輸出的答案。這幅圖，就是 決策樹模型。
關於這棵樹的兩個事實，是後續一切的引擎。第一，在某個特定輸入上執行演算法，恰好描出一條由根到葉的路徑，而它在該輸入上所做的比較次數，就是那條路徑的長度。所以最壞情況的比較次數，就是樹的高度——最長的那條由根到葉的路徑。第二，一旦演算法與輸入規模 n 固定，這棵樹就固定了。同樣規模的不同輸入會把你送往不同路徑，但它們都在同一棵樹裡遊走。演算法就是那棵樹。
a1 < a2 ?
/ \
yes no
/ \
a2 < a3 ? a1 < a3 ?
/ \ / \
[1,2,3] ... ... [3,2,1]
(a leaf = (each leaf is one
one output) possible answer)數葉子：資訊論論證
現在來到把一幅圖變成一條定理的飛躍。從問題那一側、而非演算法那一側來看葉子。一個正確的演算法必須能夠產生問題可能要求的每一個答案。所以這棵樹必須為每一個相異的正確答案至少配一片葉子。若兩個真正不同的輸入要求兩個不同的輸出，它們就必須止於兩片不同的葉子——否則演算法會對兩者給出相同答案，而至少對其中一個是錯的。這就是 資訊論下界的核心：要有足夠多的葉子來分辨每一種情況。
而一棵二元樹無法在矮小的高度底下藏住許多葉子。每次比較只有兩種結果，所以高度為 h 的樹至多有 2^h 片葉子——每多一層，葉子數最多翻一倍。反過來說：若這棵樹至少需要 L 片葉子，它的高度就必須滿足 2^h >= L，也就是 h >= log2(L)。既然高度就是最壞情況的比較次數，對於擁有 L 個相異答案的問題，任何比較演算法在最壞情況下都至少需要 log2(L) 次比較。整套論證只有兩個短步驟：數出你必須分辨的答案數，然後取個對數。
- 固定比較模型與輸入規模 n，於是演算法是一棵固定的二元決策樹。
- 數出 L = 問題在規模 n 下可能要求的相異正確答案數。
- 論證這棵樹至少需要 L 片葉子：不同的所需答案，逼出不同的葉子。
- 高度為 h 的二元樹至多有 2^h 片葉子，故 2^h >= L，因此高度 h >= log2(L)。
- 高度就是最壞情況的比較次數，所以 log2(L) 次比較無可避免。
初嚐滋味：它解釋了二分搜尋
讓我們把這台機器跑在我們已經信任的東西上，感受它給出正確的答案。考慮在 n 個元素的已排序陣列中搜尋：回報目標匹配到哪個位置，或回報不存在。相異的答案是「位置 1」、「位置 2」、……、「位置 n」，再加上「找不到」——算作 n+1 種結果。配方說：任何比較式搜尋在最壞情況下至少需要 log2(n+1) 次比較。這恰好就是 二分搜尋的 Theta(log n) 成本，而現在我們知道它不只是一個好方法——沒有任何比較式方法能在漸進上做得更好。已排序搜尋下界是決策樹最溫和的樣貌。
注意這個下界主張了什麼、又沒主張什麼——正是第一篇所堅持的那份誠實。log2(n+1) 是在這一個模型裡、最壞情況的比較次數。它對真實牆鐘時間的常數因子隻字未提，對快取行為隻字未提，對直接讀取鍵值的模型也隻字未提。它是關於資訊結構的陳述：要用是／否問題從 n+1 種可能中挑出一種，你必須問其中約 log2(n+1) 個。這就是為什麼這類下界被稱為資訊論的——它在數你被迫抽取出多少位元的答案。
這個模型能觸及與不能觸及的東西
下一篇會把這個兌現成頭條結果：排序 n 個元素，答案共有 n! 種可能的排列，所以樹需要 n! 片葉子，而 log2(n!) 算出來是 Theta(n log n)。這一道計算，就是著名的比較排序障壁——而決策樹正是它成立的全部理由。但在抵達那裡之前，值得對這個模型的觸及範圍保持清醒。這套論證在比較模型之內是精確的，在其外則保持沉默：它從不束縛計數排序、從不束縛做雜湊的演算法、也從不束縛任何不透過比較就觸及數值的東西。
決策樹也不是唯一的下界工具，而且它有盲點。它乾淨地數比較，但對更微妙的問題——你想展示某個特定的困難輸入——它說得不多；對於那些情況，第 4 篇的 對手論證更為銳利，它想像一個對手，盡量回答每次比較好讓演算法被蒙在鼓裡愈久愈好。而當某個問題的困難度最好藉由倚靠另一個問題來展現時，第 5 篇的 歸約會把下界搬運過去。決策樹是這些後續工具所立足的基礎，而非最終定論。
關於在人類尺度上解讀這些下界，最後一個誠實的告誡。最壞情況的比較次數是漸進的、結構性的陳述；它不是對每一個 n 的判決。若元素很龐大，log2(n) 次比較每一次都可能很慢，而帶著極小常數的 O(n^2) 方法，對小輸入仍可能勝過一個對數最佳的方法——就是漸進那一階所再三強調、大O符號會隱藏常數的那份提醒。決策樹告訴你成本真正的形狀。它不保證今天在你筆電上碼錶跑得最快。