3.2 对手论证

算法的改进过程中，会有一个问题：改进的界限在哪里？这一改进的界限，可以通过算法问题的下界来刻画。
例如，通过决策树可以证明比较排序的最坏情况时间复杂度的下界是 。
对于选择问题，可以使用决策树来分析下界，但是得不到充分紧的下界，因此引入对手论证分析选择问题的下界。

1. 对手论证的基本形式

可以将对手论证形象地看成两种角色之间的较量，较量的双方是算法的设计者和设计者的对手：

• 设计者：可以采用任何理论、技术来优化算法的设计，提升算法性能。对于所有合法的输入，都必须保证算法的输出是正确的。
• 对手：在所有合法的输入中，挑选对于算法最不利的“坏”输入，使算法付出更多的代价。

对手论证基本原理：通过对手论证构造坏的输入，使任何算法总是至少付出一定的代价，而这一“至少要付的代价”，就是我们要求的算法问题的下界。

2. 选择最大或最小元素

直接用蛮力方法的顺序查找，可以得到最大或最小元素，此时问题的关键在于证明算法的下界是 。

定理 对于选择最大最小元素问题, 基于比校的选择算法的最坏情况时间复条度是 n-1, 即任何基于比较的选择算法, 在最坏情况下至少要做 n-1 次比较才能选出最大最小元素。

证明 要证明至少需要 n -1次比较,等价于证明如果比较次数小于等于n-2, 则算法一定不正确。 我们使用反证法。假设对于任意合法的输入，一个算法总是能正确找到最大元素, 并假没算法至多只需要n-2次比较。假设算法选定的最大元素是 a , 由于算法的比较次数不超过n-2, 所以至少有一个元素 b， 它没有跟 a 进行过比较, 由于 b 没有和 a 进行过比较, 所以算法并不知道这两个元素之间的大小关系。所以从对手的角度, 我们把 b 的值设为大于 a 的某个合法值, 这就导致算法的错误。由此就证明了算法至少要进行 n-1 次比较。

3. 同时选择最大和最小元素

3.1 蛮力算法

首先选出最大元素，其次在剩下的元素中选出最小元素。
最坏情况代价为 n - 1 + n - 2 = 2n -3。

3.2 改进算法

通过元素两两配对比较，再从配对比较的较大元素中选择最大的元素，从配对比较的较小元素中选择最小的元素。
最坏情况代价为

3.3 下界证明

总的比较次数：

4. 选择次大元素

5. 选择中位数