给定 n 个数字，如何使用最多 n+log(n) 次比较找到最大和第二大数字？
请注意，这不是 O(n+log(n))，而是真正的 n+log(n) 次比较。
帕杰顿发表了评论。
让我详细说明一下。
正如帕杰顿所说，这可以通过锦标赛选择来完成。
可以将其视为淘汰赛单打网球锦标赛，其中球员的能力有严格的顺序，并且比赛的结果完全由该顺序决定。
第一轮就有一半人被淘汰。在下一轮中，还有一半等（可能会有一些轮空）。
最终获胜者将在最后一轮中决出。
这可以被视为一棵树。
树的每个节点都将是该节点的子节点之间的比赛的获胜者。
叶子是玩家。第一轮的获胜者是叶子的父母等。
这是一个有 n 个节点的完全二叉树。
现在，沿着胜利者的道路前进。获胜者已经参加了 log n 场比赛。现在考虑那些 log n 场比赛的失败者。第二好的一定是其中最好的。
在 n-1 场比赛中决出胜者（每场比赛淘汰一场），而 logn 中的胜者则在 logn -1 场比赛中决出。
因此，您可以在 n+logn - 2 次比较中确定最大和第二大。
事实上，可以证明这是最优的。在最坏情况下的任何比较方案中，获胜者都必须进行logn比赛。
为了证明这一点，假设采用积分制度，在比赛结束后，获胜者获得失败者的积分。最初，所有人都以 1 分开始。
最终获胜者获得n分。
现在给定任何算法，都可以安排为拥有更多分数的玩家总是获胜者。由于在这种情况下，任何人在任何比赛中的分数最多都会翻倍，因此在最坏的情况下，您至少需要获胜者参加的 n 场比赛。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
