決策樹模型（decision-tree model）

把一個演算法想成一張是非問題的流程圖。你從頂端出發，問一個關於輸入的問題，依答案往左或往右走到下一個問題，如此繼續，直到抵達一個宣布答案的葉子。決策樹正是這張圖：內部節點是比較、葉子是可能的輸出的一棵樹。它是一種「把任何基於比較的演算法畫出來」的辦法，好讓我們用幾何方式推理它。

以排序為例該怎麼讀。每個內部節點放一個比較，像「A[i] < A[j] 嗎？」；兩個子節點是「是」與「否」的後續。某個特定輸入會從根走到某一片葉子，而那片葉子必須說出該輸入正確的排序順序（即排列）。因為演算法是決定性的，相同順序的相同比較永遠把某個輸入送到同一片葉子。該輸入在最壞情況下花的比較次數，就是最深葉子的深度——也就是樹高。於是「最佳演算法的最壞情況比較次數」變成「正確決策樹可能達到的最小樹高」，一個我們能加以界定的乾淨組合量。

這種重畫正是最著名下界背後的引擎。要正確，這棵樹對演算法可能產生的每一個相異輸出，至少都得有一片葉子；一棵有 L 片葉子的二元樹，樹高至少為 log2(L)；所以最壞情況比較次數至少是 log2(L)。對 n 個元素排序有 n! 種可能順序，逼出 L >= n! 與樹高 >= log2(n!) = Omega(n log n)。這個模型對自身適用範圍很誠實：它只刻畫「唯一學習輸入的方式是比較」的演算法，而它所量的「成本」是比較次數，忽略搬動元素之類的雜務——這沒問題，因為那些雜務步驟不可能比驅動它們的比較還便宜。