資訊理論下界（information-theoretic lower bound）

想想小孩玩的「二十問」遊戲。如果我心裡想著一百萬件東西中的一件，你問的每個是非問題頂多把可能性砍一半，所以你至少需要約 log2(1,000,000) = 20 個問題才能確定。沒有任何策略能更好，因為每個問題最多買到一個位元的確定性。資訊理論下界正是把這個想法變成一種證明技巧：要從眾多答案中鎖定一個，你必須蒐集足夠的位元資訊，而每個便宜的操作只提供有限的量。

這個配方有兩種材料。第一，數出演算法可能必須輸出的相異答案數——叫它 M。要區分 M 種可能性，至少需要 log2(M) 個位元的資訊。第二，界定一個基本步驟揭露多少資訊。在比較模型中，單次比較有三種結果（<、=、>），但通常被當作至多一個有用位元的是非，所以任何正確演算法在最壞情況下至少需要 log2(M) 次比較。這一個論證就交出了兩個招牌下界：排序有 M = n! 個答案，給出 log2(n!) = Omega(n log n)；搜尋有序陣列有 M = n+1 個結果，給出 log2(n+1) = Omega(log n)。

小心使用時，這是一個乾淨而通用的工具，但它有你必須尊重的實質侷限。它只界定「蒐集資訊」的步驟；如果每一步能揭露「不只一個」位元，地板就相應下降——一個讀取整個機器字組的操作會洩漏許多位元，這正是基數排序逃脫 n log n 障礙的原因。它也是最壞情況、計數風格的論證：它證明「某些」輸入需要這麼多工作，卻不指出是哪個，而且通常給出正確的數量級而非精確常數。當單次比較能給超過一個位元時（三向比較給出至多 log2(3) 個位元），謹慎版本改用 log_3 而非 log_2，這會改變常數但不改變 Omega。