找最大值的下界（lower bound for finding the maximum）

要找 n 個數中最大的，自然的方法是掃一遍：握著一個目前的冠軍，拿它和下一個元素比，留下較大的。這用 n-1 次比較。更聰明的方案能用更少嗎？下界說不行：任何基於比較的演算法在最壞情況下都至少需要 n-1 次比較才能找到最大值。這個簡單的掃描恰好最優——沒有聰明的餘地。

最乾淨的證明是「淘汰賽」或記帳論證。把最大值想成淘汰賽的唯一贏家：一個元素只有在輸掉至少一次比較後，才能被排除為最大值。共有 n 個元素，除了一個（真正的最大值）之外都必須被淘汰，所以至少 n-1 個元素各得吃一場敗仗。但單次比較恰好產生一個輸家。因此要製造 n-1 場敗仗，你至少需要 n-1 次比較。對手讓這滴水不漏：它回答每次比較時，讓被報出的輸家是某個從未輸過的元素（只要還有兩個全勝元素，這永遠可行），保證每次比較最多淘汰一個新候選，所以少於 n-1 次比較會留下兩個都仍可能是最大值的元素。

這是一個令人滿足的案例：顯而易見的演算法與下界恰好在 n-1 握手，所以這問題的比較複雜度精確就是 n-1——不只是 Theta(n)，而是確切次數。誠實的範圍註記：這是比較模型、最壞情況的下界；它數比較次數，不數資料搬動；而且它只關乎找「最大值」。要求更多——同時找最大與最小、或第二大、或中位數——都會改變次數，各有自己更緊的分析。特別是，同時找最大與最小「並不」花 2(n-1)；更聰明的配對能做得更好，下一條會解釋。