作者：劉子韜
為什麼需要下界？
上界告訴我們「能做到什麼程度」，下界告訴我們「絕對做不到什麼程度」。Lower bounds tell us what cannot be done, guiding search for what can be done.
例：歸並排序 O(n log n)，但能否更快？需證明 Sorting = Ω(n log n)。
兩大下界證明方法
- 決策樹法：分析算法決策過程樹高度下界（《算法導論》標準法）
- 對手論證法：構造對手策略，迫使算法執行更多步驟，往往能得更緊確下界
經典案例：基於比較的排序下界
決策樹法證明 Ω(n log n)
- n 個元素全排列 n! 種 → 決策樹葉子 ≥ n! 個
- 二叉樹高度 h，葉子 ≤ 2ʰ
- n! ≤ 2ʰ → h ≥ log(n!) = Ω(n log n)
- 對任意比較排序算法成立
對手論證法證明 Ω(n log n)
- 對手維護候選排列集合 S，初始 |S| = n!
- 每次比較詢問，對手回答使剩餘候選集盡可能大（≥ 半數）
- 需將 |S| 從 n! 縮減至 1 → 至少 log(n!) 次詢問
- 若詢問 < log(n!) 次，|S| ≥ 2，對手總能給出反例令算法失敗
平均情況下界同為 Ω(n log n)
- 平均情況 = 決策樹所有葉子深度平均值
- 平均深度最小的樹是完全平衡二叉樹
- 非平衡樹可將最深葉子接到最淺分支降低平均深度
- ∴ 平均深度 ≥ 平衡樹深度 = Ω(n log n)
隨機化算法下界同為 Ω(n log n)
雅翁原理：對任意輸入分布，確定性算法期望代價 ≥ 最壞情況下界。隨機算法本質是確定性算法的概率分佈，下界同理成立。
更多下界證明例題
例 1：合併兩個有序列表（長度均為 n）
下界：2n - 1 次比較
對手論證：
- 假設只比較 2n-2 次
- 存在某 aᵢ 未與 bⱼ 或 bⱼ₊₁ 比較
- 設 aᵢ = 2i-1 (奇數)，bⱼ = 2j (偶數)
- 對手交換 aᵢ 和 bⱼ (或 bⱼ₊₁) 值，保持有序性但改變合併結果
- 算法輸出錯誤 → 矛盾 → 至少需 2n-1 次比較
例 2：有序表查找元素 x
下界：⌈log₂(n+1)⌉ 次比較
決策樹法：
- n 個可能答案 → n 個葉子
- 二叉樹高度 h，最多葉子 2⁰+2¹+...+2ʰ⁻¹ = 2ʰ - 1
- 2ʰ - 1 ≥ n → h ≥ log₂(n+1)
總結
下界分析是算法理論皇冠上的明珠。決策樹法直觀通用，對手論證法靈活強大。關鍵洞見：
- 比較模型下排序 Ω(n log n) 是鐵律
- 平均/最壞/隨機化下界往往同階
- 對手策略設計是藝術：需構造具體輸入族迫使算法「盲區」暴露
- 掌握下界思維，才能知道何時停止優化、接受現狀或尋找新模型（如非比較排序）
