一道我們一直繞著的牆
你已經見過合併排序，它以 O(n log n) 時間 把 n 個鍵值排好，也見過隨機快速排序，其期望時間同樣是 O(n log n)。很自然會想：這只是目前最聰明的人想到的最好辦法，還是真正的地板？這正是先前指南教我們要認真看待的問題——一個 問題的下界 是關於任務本身的陳述，對每一個現在與未來的演算法都成立，而不是某個方法的招供。本篇將證明，對於用比較進行的排序，n log n 確實是一道牆。
一切都取決於我們計算的是什麼，所以先把規則定好。在 比較模型 中，演算法認識鍵值的唯一途徑，是問形如「a[i] <= a[j] 嗎？」的問題，並依是／否的答案分支。它不可以偷看鍵值的位元、對它做雜湊、把它當陣列索引，或對它做算術。許多人鍾愛的排序器——合併排序、快速排序、堆積排序、插入排序——恰好都遵守這些規則，所以這個模型裡的一個下界一次就道盡了它們全體。
每個比較排序器都是一棵樹
上一篇指南給了我們關鍵的工具：決策樹。取任何一個比較排序器，讓它在固定大小 n 的輸入上執行，為它做的每一次比較畫一個節點。每個內部節點是一個問題「a[i] <= a[j] 嗎？」，帶有兩個子節點，一個對應「是」，一個對應「否」。某個特定輸入會走出一條從根到葉的單一路徑，沿途回答每個問題，而當演算法終於停下時，它抵達的那片葉子必須宣告排好的順序。演算法對於每個大小為 n 的輸入的全部行為，都被凍結進這一棵樹裡。
現在是關鍵的計數一步。葉子是可能的答案，而一個正確的排序器必須能輸出每一種可能的排好順序。對於 n 個相異的鍵值，共有 n! = n * (n-1) * ... * 2 * 1 種不同的順序——輸入可能處於的 n! 個相異排列。兩個不同的正確答案不能共用一片葉子：如果兩個需要不同輸出順序的輸入都停在同一片葉子，那片葉子至多只能正確印出其中一個。所以這棵樹必須有 至少 n! 片葉子，每個它必須產生的排列各有一片可達的葉子。
這裡是從葉子通往執行時間的橋。演算法在某個給定輸入上所做的比較次數，就是那個輸入從根到葉的路徑長度。因此 最壞情況 的比較次數，就是最長的那條路徑——也就是樹的高度。所以只要我們能證明任何擁有 n! 片葉子的二元樹都必定很高，我們就證明了任何比較排序器在某個輸入上都必須做那麼多次比較。這個論證悄悄地把一個關於演算法的問題，轉化成了一個關於樹的形狀的問題。
矮樹裝不下足夠的葉子
一棵高度為 h 的二元樹至多有 2^h 片葉子——這是關於樹最簡單的事實，也是整個證明的引擎。原因在於每一層至多讓節點數加倍：根是 1，第 1 層至多 2，第 2 層至多 4，第 h 層至多 2^h。一片葉子只能住在深度至多 h 之處，所以葉子數不超過 2^h。矮樹的葉子稀少；要裝下許多葉子，你就得長高。
把這兩個事實合起來。樹需要至少 n! 片葉子，但至多只能裝 2^h 片，所以必定有 2^h >= n!。對兩側取以 2 為底的對數：h >= log2(n!)。光是這一個不等式就已經說了：高度——也就是任何比較排序器最壞情況的比較次數——至少是 log2(n!)。剩下要做的，只是看清 log2(n!) 大約就是 n log n，而不是更小的東西。
leaves needed >= n! (one per permutation) leaves possible <= 2^h (binary tree of height h) => 2^h >= n! => h >= log2(n!) = Omega(n log n)
為什麼 log2(n!) 的數量級是 n log n？一個乾淨的估計可以避開任何笨重的機器。n! 中前半部的那些因子——共有 n/2 個，每個至少是 n/2——給出 n! >= (n/2)^(n/2)。取 log2，那至少是 (n/2) * log2(n/2)，也就是 Theta(n log n)。（著名的斯特靈近似把它釘得更精確：log2(n!) = n log2 n - n log2 e + O(log n)，但我們不需要那種精度；這個粗略的界已經把我們帶到 Omega(n log n)。）所以高度是 Omega(n log n)，證明就完成了。
同一個證明，用資訊的語言來說
這個論證還有第二種說法，許多人覺得更好記：資訊理論 觀點。把排序想成是在辨認你的輸入暗中究竟是 n! 個排列中的哪一個。每次比較回傳單一個是／否的位元，而一個位元至多能把仍然可能的排列集合切成一半。要靠反覆對半切，把一個大小為 n! 的集合縮到只剩一個倖存者，你至少需要 log2(n!) 次對半——至少 log2(n!) 個位元——這正是同一個 Omega(n log n)。
這不是另一個定理；它是決策樹論證換了一身衣服。「一個位元把候選對半」恰恰就是「一個分支節點有兩個子節點」；「需要 log2(n!) 個位元才能鎖定一個排列」恰恰就是「需要至少 log2(n!) 的高度才能抵達 n! 片相異的葉子」。有些讀者偏好樹的畫面，因為它具體又視覺化；另一些人偏好資訊的畫面，因為「一次比較產出一個位元，而你需要學到 log2(n!) 個位元」這句話把整個想法壓縮成一句。兩者都留著吧；它們互相印證。
這道障壁說了什麼、沒說什麼
首先，這個界計算的是比較次數，不是實際秒數。一個做 Omega(n log n) 次比較的方法，在小 n 時仍可能很慢，那裡是常數因子與快取行為當家；合併排序乾淨的漸進表現，並不妨礙函式庫在極小的子陣列上改用插入排序。這道障壁描述的是某種特定成本（比較次數）的規模化，而漸進分析一如既往地隱藏了常數——它告訴你沒有比較排序器能勝過的成長率，而非在 n = 16 時哪個排序器會贏。
其次，這道障壁是可被觸及的，這正是它令人滿意而非僅僅令人沮喪之處。合併排序在最壞情況下做 O(n log n) 次比較，所以它的比較次數是 Theta(n log n)：我們剛證明的 Omega(n log n) 地板，與合併排序 O(n log n) 的天花板恰好相遇。一個下界與一個觸及它的演算法合在一起，釘住了問題真正的難度——這是整個演算法分析裡最快樂的結局，一個從上下兩側都被完整回答的問題。
第三，同一套數葉子的範本，遠遠不只用於排序。在一個有 n 個鍵值的已排序陣列中搜尋的下界——log2(n+1) 次比較——來自一棵必須區分 n+1 種可能結果的樹。這個界也是更難的決策樹結果的種子：元素相異性與凸包在它們各自更豐富的模型裡都需要 Omega(n log n) 次操作，證法同樣是計算這棵樹必須分開多少個相異的答案。你剛學到的技巧是一把萬能鑰匙，而非一次性的把戲。
這篇的位置，以及接下來是什麼
退一步，留意我們所做之事的形狀，因為它是一道可重複使用的食譜。整個證明是一個 計數論證：數出一個問題能有多少個相異的正確答案，觀察到一個低分支度的計算若不執行得夠久，就無法分開太多答案，從而推出一個高度——也就是一個時間——下界。我們沒有檢視任何特定演算法；我們透過對它們共享的模型進行推理，一次就對每一個演算法都做了推理。
- 固定一個模型，明確說出一步是什麼——在這裡是一次比較，並把比較模型的限制講清楚。
- 數出問題要求的相異正確輸出——在這裡是 n! 個排列，因而至少有 n! 片葉子。
- 為一個給定長度的計算能分開多少個輸出定界——一棵高度為 h 的二元樹至多分開 2^h 個。
- 解出長度：2^h >= n! 逼出 h >= log2(n!) = Omega(n log n)。
決策樹很強大，但它有一個盲點：當答案眾多且容易計數時它大放異彩，而當一個問題只有一兩個可能答案時——例如「最大值是多少？」——它就力不從心。對於那些問題，下一篇指南轉向一種不同且更具對抗性的技巧——對手論證，一個想像中的對手會在規則允許的範圍內以最殘忍的方式回答你的比較，無論你問得多巧妙都逼你做工。在那之後，本階以歸約得出的下界作結：透過把一個已知困難的問題偷渡進新問題裡，來證明新問題很難。