对手下界方法

形式陈述 ​

在固定查询模型中，对手面对确定性算法的每次查询选择一个合法回答，并维护非空候选集合 $C$，其中每个输入都与此前全部问答一致。若对手能保证少于 $q$ 次查询后仍有两个候选输入需要不同输出，则任何正确算法的最坏查询数至少为 $q$。回答可以延迟决定具体输入，但结束时必须存在一个单一合法输入同时实现完整问答历史。

这一过程等价于在决策树公理库决策树模型Decision-tree model · Comparison decision tree用查询节点、答案分支和输出叶刻画算法能够区分输入所需的信息深度。中，根据算法选定的节点挑选一条最坏分支。下界的单位、可问查询和答案集合必须先固定；用比较对手得到的界不能自动套到允许算术、哈希或批量查询的更强模型。

直觉 ​

算法只看见已经询问的信息，对手便尽量推迟会缩小候选集的承诺。它不是运行中篡改一个秘密输入，而是持续维护一组仍能解释全部答案的输入；最后任选其中一个，算法在这条真实输入上确实经历了同样的困难路径。

有效证明需要一个可量化不变量，例如“仍可能是最大值的元素数”或“尚未区分的排列数”。只说对手总给最麻烦答案，不足以证明这些答案彼此兼容，也无法推出查询次数。

例子与边界 ​

考虑只允许两两比较、要求找出 $n$ 个互异元素最大值的问题。初始每个元素都可能最大。对手对每次比较任选一个尚未矛盾的方向，并把失败者标记为“不再可能最大”；一次比较至多淘汰一个候选。正确结束时必须只剩一个候选，因此至少需要 $n-1=\mathrm{\Omega }(n)$ 次比较。

全局一致性可由比赛有向图说明：把胜者指向败者，对手始终保持图无环；任一拓扑序都能赋予互异数值，使所有已答比较同时成立。算法若在两个未输过的元素仍存在时停止，可选拓扑序让任一个成为最大，故同一输出不可能对两种补全都正确。

这个证明只得到确定性比较下界。随机算法的期望下界不能直接让对手看见随机位后逐步针对；通常需要固定困难输入分布并使用 Yao 原理。证书“某元素击败所有相关对手”也不等于算法已经比较了所有必要对，因为比较关系的传递性必须在模型中明确使用。

推论与应用 ​

对手法可证明选择、搜索、在线算法和数据结构查询下界。设计时应依次写清候选对象、回答策略、不变量、每次查询最多减少多少不确定性，以及最终两个不同输出的可实现补全。

与叶数法相比，对手法更容易利用问题结构和自适应查询；两者都在追踪可区分信息。若对手不变量无法给出紧界，信息论计数、通信复杂度或 cell-probe 技术可能更合适。

参考资料

• Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974, Ch. 6.
• Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998, §5.3.3.