另一種把問題變難的方式
前幾篇指南是靠數葉子擠出一個 下界：一棵能區分 N 種可能答案的 決策樹，深度至少要 log2(N)，這就導出了著名的比較排序障壁。那個計數論證很有力，但有點抽象——它談的是整棵結果樹。對手論證 是同一個想法換上更鮮明的戲服：我們不再數葉子，而是雇用一位惡意的裁判來回答你的提問，並證明這位裁判總能拖住你，直到你做了一定量的工作為止。
情境是這樣的。我們在 比較模型 中工作，所以你的演算法只能透過提出像「x[i] 是否小於 x[j]？」這樣的比較問題來認識輸入。關鍵在於：對手並未事先把輸入固定下來。它即時回答每個問題，挑選那個能讓最多不確定性存活的回覆——它唯一必須遵守的規則是：永遠至少要保留一個與它目前所有回答都一致的具體輸入。只要它守得住這個承諾，它的回答就是合法的，而你的演算法分辨不出它與一個誠實地讀取真實陣列的神諭有何不同。
關鍵在於，對手並沒有作弊。它從不說謊，因為每一步它的回答都與某個真實的輸入保持一致。它只是延後對那個輸入做出承諾，就像一位老練的主考官，回答你的猜測時剛好誠實到足以讓你繼續摸索。如果你的演算法在還有兩個不同輸入與所有回答都一致時就停手，那這兩個輸入可能對應不同的正確輸出——所以提早停手就意味著停在錯誤上，而這正是整套技術所倚仗的施力點。
暖身：找最大值需要 n-1 次比較
從最乾淨的情況開始。要在 n 個相異數字中找出最大者，最直白的方法掃描一遍，一路保留當前的擂主，用掉 n-1 次比較。更聰明的方法能用更少嗎？找最大值的對手下界 說不行。這個論證是一段優美的記帳：稱一個元素在它某次比較落敗的那一刻為 輸家。一個從未落敗的元素，就目前所知，仍然有可能是最大值。
現在看對手如何記分。每個元素一開始都是可能的最大值。要正確地回報出那個最大值，你的演算法必須排除其餘 n-1 個候選者，而一個候選者只能透過在比較中落敗——成為輸家——來被排除。對手一致地回答每次比較（比方說，偷偷指派它仍可調整的數值），但關鍵的觀察在於：兩個元素之間的單次比較，最多產生一個新的輸家。如果兩者本來就都是輸家，沒有新候選者被淘汰；如果其中一個是新鮮的，也只有那一個倒下。所以每次比較最多劃掉你必須淘汰的 n-1 個候選者中的一個，於是總共逼出至少 n-1 次比較。
同時求最大與最小：為何代價是 3n/2 - 2
現在改成同時要求 n 個數字的最大值「與」最小值。偷懶的做法用 n-1 次比較找最大值，再用 n-2 次找最小值，總共約 2n 次。但你可以靠配對做得更好：每次兩兩比較，把每對中較大者送進一場最大值錦標賽、較小者送進一場最小值錦標賽。這大約花 3n/2 次比較。這個配對技巧只是聰明，還是真的最優？最大與最小的對手論證 證明它本質上是最優的：你無法擊敗大約 3n/2 - 2 次。
這一次對手記一本更豐富的帳。它為每個元素標記它還有多「未定」：一個元素若從未被比較過是「新鮮的」，若只贏過是「贏家」，若只輸過是「輸家」，若既贏過又輸過則是「已知」（於是它既不可能是最大也不可能是最小）。要完成任務，演算法需要 n-1 個元素被確認不是最大值、n-1 個被確認不是最小值；用標籤的話說，除了一個之外所有元素都必須是「贏家或已知」（被排除於最小值之外），且除了一個之外都必須是「輸家或已知」。對手的工作，就是在規則允許下，讓每次比較帶來的進展盡可能少。
關鍵的洞見是：唯一能一次帶來「兩」單位進展的比較，是新鮮對新鮮的比較：它能把一個新鮮元素變成贏家、另一個變成輸家，兩邊的計數同時前進。其餘任何種類的比較，最多只讓記帳前進一單位，而對手總是這樣回答以確保如此（例如，當一個贏家遇上一個新鮮元素，它宣告贏家較大，於是新鮮者成為輸家、贏家學不到新東西）。n 個元素中，這種雙重有效的新鮮對新鮮比較至多只有 n/2 次，剩下所需的進展必須一單位一單位地累積。把它加起來就得到 3n/2 - 2 的界——證明配對演算法不只是個漂亮的把戲，而是真正的地板。
label counts start: Novel = n, others = 0 Novel vs Novel -> +2 progress (>= 1 win, >= 1 loss minted) any other pair -> +1 progress (adversary forces this) needed progress = (n-1) + (n-1) = 2n - 2 at most n/2 comparisons give +2; rest give +1 min comparisons >= (n/2) + (2n - 2 - 2*(n/2)) = 3n/2 - 2
邁向中位數：塑造偏序的對手
選出 中位數——如果陣列被排序後會坐在正中間的那個元素——更難給出下界，它把這項技術推到了極致。一個基於比較的選擇器會學到元素之間的一個偏序，而要證明某元素 m 是中位數，它必須累積足夠的比較，來證明恰好有一半元素在 m 之下、一半在 m 之上。對手的策略是這樣回答比較：讓這份證書盡可能離完成很遠，在被逼之前，拒絕讓任何元素承諾自己明顯偏小或明顯偏大。
對手做到這點的一個乾淨方式，是不斷暫定地指派與已給回答一致的數值，總是把一個剛被觸及的元素擺到能延長搜尋的那一側——把界線附近的元素推向中位數的鄰域，讓它們維持曖昧。透過輸家計數記帳的一個更精細版本，可以證明中位數選擇至少需要大約 2n 次比較，舒舒服服地多於最大值所花的 n-1 次。這和最大值證明是同一套機械裝置，只是追蹤的位勢更微妙：不是「還有多少候選者存活」，而是「偏小側／偏大側的證書還有多不完整」。
為何這與決策樹是同一回事——以及它在何處發光
對手論證與數葉子論證是同一枚硬幣的兩面。數葉子說：有 N 種可能答案，所以樹很深。對手說：我會帶你走下這棵樹，在每個節點我挑選那個能讓最大一束一致輸入存活的子節點，所以在你做足夠多的比較把那束縮小到單一答案之前，你抵達不了葉子。兩者都證明了 Omega(n log n) 的 比較排序下界；對手版本往往讓論證更具體，而當你在乎精確常數時它是更好的工具，正如最大值與最大-最小的結果所示。
不過要誠實地交代適用範圍。這裡的每一個界都活在比較模型之內：它計算的是比較次數，對於那些直接利用數值本身的演算法，它隻字未提。計數排序與基數排序之所以真的能在 O(n) 時間內排序，正是因為它們不是基於比較的——它們打破了模型的假設，所以 Omega(n log n) 這層地板對它們根本不適用。對手論證是關於某個模型的陳述，從來不是無條件的自然法則，而指明模型正是正確陳述結果的一部分。
- 固定模型與提問的種類（只能比較），讓演算法的每一「步」被允許學到什麼變得清楚。
- 選一個位勢——一個開始時遠未完成、且在演算法可以正確停手前必須達標的量（被淘汰的候選者、證書的完整度、存活的輸入）。
- 給對手一條回答規則，它總是與某個真實輸入一致，卻讓每次比較最多只推進位勢一小步。
- 用目標進展除以每步的最大進展，讀出該問題的比較次數下界。