2. 对手论证下界证明¶

我们要考察的下一个问题，是在一组对象中找出第二大的值。 想象我们在举办一场标准的单淘汰制（single-elimination）锦标赛。 我们打算把事情过度简化，假定各队有一个真实的"名次排序（rank order）"，并且如果一队的排名比另一队"更高"，那么它总是在两者之间的任何比赛中获胜。 那么，即便我们假定"最好"的队每场比赛都获胜，第二名就一定是决赛中输掉的那个吗？ 未必如此。 我们或许预期第二好的队一定会输给最好的队，但二者可能在任何时候相遇。

让我们按标准的"寻找算法的算法"流程走一遍：先提出一个算法，再提出一个下界，看看它们是否吻合。 在渐近意义上，代价会是多少几乎是一目了然的，并不那么有趣。 然而，与我们分析大多数问题不同，这次我们要数一数所涉及的比较的 精确次数 ，并设法使这一次数最小。 毕竟，让两支队伍打一场比赛要耗去不少工夫！

寻找第二大的一个简单算法是：先找出最大值（ \(n-1\) 次比较），把它丢弃，再在剩余元素中找出最大值（ \(n-2\) 次比较），总代价为 \(2n-3\) 次比较。 这是最优的吗？ 看起来似乎存疑，不过现在让我们进入下一步，尝试证明一个下界。

这个证明是错误的。 它犯了 必然性谬误 ： "我们的算法是这样做的，因此解决该问题的所有算法也必然这样做。" 没有理由要求最大元素必须与每个其他元素直接比较。 即使最基本的标准求最大算法，也不需要发生这种情况。

这样一来，目前我们默认的最佳下界论证只能是：找出第二大值至少要花与找出最大值一样多的代价，即 \(n-1\) 。

让我们换种方式，采用分治策略再来尝试找出更好的算法。 如果把线性表分成两半，并对每一半运行 largest ，会怎样呢？ 这需要 \(n-2\) 次比较。 然后我们比较两个获胜者（至此我们总共用了 \(n-1\) 次比较），并把获胜者从其所在的那一半中移出。 再次对获胜者所在的那一半（去掉获胜者之后）调用 largest ，就能以 \(n/2 - 1\) 的代价得到这一半的第二好。 最后与另一半的获胜者比较一次，就得到真正的第二名获胜者。 总代价是 \(\lceil 3n/2\rceil - 2\) 。 这是最优的吗？ 如果把线性表分成四份呢？ 最好大约为 \(\lceil 5n/4\rceil\) 。 如果分成八份呢？ 那么代价大约为 \(\lceil 9n/8\rceil\) 。 但请注意，当把线性表分成更多部分时，各部分获胜者之间的比较就变得越发重要。

换一个角度看，第二名的唯一候选者是那些输给最终获胜者的失败者，而我们的目标是让这些失败者尽可能少。 因此，我们需要跟踪那些在直接比较中输给（最终）获胜者的元素集合。 我们还观察到，当两个竞争者的已知大于其他值的个数相同时，一次比较能让我们学到最多。 所以我们希望把比较安排在"势均力敌"的竞争者之间。 要做到这一切，可以用 二项树 。 一棵高度为 \(m\) 的二项树有 \(2^m\) 个结点。 它要么是单个结点（若 \(m=0\) ），要么是两棵高度为 \(m-1\) 的二项树，其中一棵树的根成为另一棵树的子结点。 我们来看看一棵有八个结点的二项树是如何构造的。

Settings

Saving...
Server Error
Resubmit

由此得到的算法原理上很简单：为全部 \(n\) 个元素构造二项树，然后比较根结点的 \(\lceil \log n\rceil\) 个子结点来找出第二名。 我们可以把二项树显式存储为一棵树结构，并轻易地在线性时间内建成它，因为每次比较只需添加一条链接。 由于二项树的形状受到严格约束，我们也可以把二项树隐式存储在一个数组中，就像对堆所做的那样。 假设有两棵树，每棵有 \(2^k\) 个结点，都在数组中。 第一棵位于位置 1 到 \(2^k\) 。 第二棵位于位置 \(2^k+1\) 到 \(2^{k+1}\) 。 每棵子树的根位于该子树在数组中的最后一个位置。

要合并两棵树，我们只需比较两棵子树的根。 必要时交换子树，使根元素较大的子树成为第二棵子树。 这是用空间（我们只需要为数据值腾出空间，不需要结点指针）换时间（最坏情况下，全部数据交换可能花费 \(O(n \log n)\) ，不过这并不影响所需的比较次数）。 请注意，对某些应用来说，数组的数据交换不需要任何比较，这是一个重要观察。 如果一次比较只是两个整数之间的检查，那么在数组中移动一半的值当然代价过高。 但如果一次比较需要两支运动队之间举行一场比赛，那么在计算机上进行一点点（甚至很多）簿记的成本就变得无关紧要了。

由于二项树的根有 \(\log n\) 个子结点，而构造这棵树需要 \(n-1\) 次比较，因此这个算法所需的比较次数为 \(n + \lceil \log n \rceil - 2\) 。 这显然比我们之前的算法要好。 它是最优的吗？

一点小小的题外话： 你可能会好奇，在这里给出二项树的用意何在。 它看起来可能令人困惑，因为你大概习惯了看到锦标赛的布局图，它展示单淘汰锦标赛中各位选手或队伍的计划赛程。 特别是，如果参赛实体的数目是 \(2^n\) ，这种锦标赛布局就是一棵平衡树，而二项树并不是平衡的。 区别在于，锦标赛树和二项树是在展示类似信息的两种视图。 锦标赛树展示的是 先验 的赛程安排。 二项树展示的是比赛的结果，例如执行锦标赛树赛程后所得的结果。 特别是，一旦某个竞争者输了，它就不再比赛（至少在常规的单淘汰锦标赛中如此）。 由于某些竞争者参赛的次数比别人少，二项树就不是平衡的。 题外话结束。

我们现在回到改进下界证明的尝试上来。 为此，我们引入 对手 的概念。 对手的工作是让算法的代价尽可能高。 设想对手保存着所有可能输入的清单。 我们把算法看成向对手询问关于算法输入的信息，而对手在每次被询问时给出回答。 对手绝不能撒谎，因为它的任何回答都必须与之前所有回答一致。 但对手被允许按照自己的意愿"重新安排"输入，以便把算法的总代价推向尽可能高（只要重新安排后的输入与先前的回答一致即可）。 特别是，当算法提出一个问题时，对手必须以与至少一个剩余输入保持一致的方式作答。 然后，对手把所有与该回答不一致的剩余输入划掉。 请记住，计算机程序中并不真的存在一个作为对手的实体，我们也没有真正修改程序。 对手仅仅充当一种分析工具，帮助我们思考程序。

作为对手概念的示例，考虑标准的猜词游戏（Hangman）。 玩家 A 挑一个词，并告诉玩家 B 这个词有几个字母。 玩家 B 猜测各种字母。 如果 B 猜中了词中的某个字母，A 就会指出这个词中哪些位置有这个字母。 玩家 B 在输掉游戏之前，只被允许猜有限次不在词中的字母。

在猜词游戏的例子中，想象对手拿着一本由若干选定长度的词组成的词典。 每次玩家猜一个字母，对手就查阅词典，判定接受这个字母（并指出它占据哪些位置）还是说它不在词中，哪个能淘汰更多的词。 只要词典中至少有一个词与所有这些决定一致，对手就可以作出它选择的任何决定。 这样一来，对手就有望让玩家尽量多猜字母。

在解释对手如何在我们找出第二好的下界证明中发挥作用之前，先注意至少有 \(n-1\) 个值必须输至少一次。 这至少需要 \(n-1\) 次比较。 此外，至少有 \(k-1\) 个值必须输给第二大的值。 也就是说，\(k\) 个输给赢家的直接失败者必须被比较出来。 因此至少要有 \(n + k - 2\) 次比较。 问题在于：我们能把 \(k\) 压到多低？

把元素 A[i] 的 强度（strength） 定义为 A[i] （已知）比之更大的元素个数。 如果 A[i] 的强度为 \(b\)，而 A[j] 的强度为 \(a\) ，那么胜者的强度为 \(a + b + 1\) 。 算法可以知道每个元素（当前的）强度，并选择接下来比较哪两个元素。 对手有权决定任意一次比较谁胜出。 对手采用什么策略，最能让算法从任意一次给定的比较中学到最少的东西？ 它应当使任何元素强度提高的速率最小。 做法是让每次比较中强度较大的元素获胜。 这是对对手的"正当"利用，因为它代表了为该给定算法提供一个最坏情况输入的结果。

为了把最坏情况行为的影响降到最低，算法的最佳策略是使强度的最小提升最大，方法是让任意两个竞争者的强度保持均衡。 从算法的角度看，最好的结果是某个元素强度翻倍。 这发生在 \(a = b\) 时，其中 \(a\) 和 \(b\) 是被比较的两个元素的强度。 所有强度都从零开始，因此当 \(2^{k-1} < n \leq 2^k\) 时，胜者必须至少进行 \(k\) 次比较。 因此，至少要有 \(n + \lceil \log n\rceil - 2\) 次比较。 所以我们的算法是最优的。