決策樹的葉子計數論證（leaf-counting argument）

這裡是那個驅動幾乎每一個比較下界的小而可重用的引理，說一次，好讓你到處套用。一棵每個內部節點至多兩個子節點、共有 L 片葉子的二元樹，不可能太矮：它的樹高至少 log2(L)。直覺上，每一層最多把葉子數加倍，所以要達到 L 片葉子，你至少需要 log2(L) 層。這就是引擎；排序與搜尋的下界只是這個引理餵入不同的葉子數。

完整論證有三個乾淨、可逐字重用的步驟。第一步，建模：把比較演算法畫成一棵二元決策樹，內部節點是比較、葉子是輸出，最壞情況比較次數等於樹高。第二步，數葉子：論證正確性逼出至少 L 片葉子，因為演算法必須能輸出它可能需要的每一個相異答案，而相異答案需要相異葉子（兩個不同的正確輸出不能共用一片葉子，因為一片葉子只承諾一個輸出）。第三步，由葉數推樹高：套用引理 樹高 >= log2(L)。對排序代入 L = n! 得到 Omega(n log n)；對有序搜尋代入 L = n+1 得到 Omega(log n)。同樣三步，不同的 L。

關於範圍與緊度的兩個誠實要點。這個引理需要「二元」分支因子：每次比較至多兩個相關結果。若某節點能三向分支（一個真正用上 <、=、> 三者的比較），把 log2 換成 log3，這改變常數但永不改變 Omega——三向分支最多省下一個常數倍。而且這個論證只有在某演算法真的達成樹高約 log2(L) 的平衡樹時才緊；一個正確的下界證明你無法做得更好，但要與之吻合需要一個真實演算法（合併排序、二分搜尋）抵達那塊地板。葉子計數論證給出地板；演算法顯示地板可達，兩者合起來把複雜度釘成 Theta。