查找最大和第二大的N个数字 [英] Finding largest and second-largest out of N numbers

问题描述

由于n个数，我怎么发现的最大和第二大使用人数最多n +的log（n）的比较？

Given n numbers, how do I find the largest and second largest number using at most n+log(n) comparisons?

请注意，这不是为O（n +的log（n）），但真正的n +日志（N）的比较。

Note that it's not O(n+log(n)), but really n+log(n) comparisons.

推荐答案

pajton给予了评论。

pajton gave a comment.

让我解释。

正如pajton所述，这可以通过锦标赛选择完成。

As pajton said, this can be done by tournament selection.

想到这是一个淘汰的单打网球赛，在那里球员的能力有严格的顺序和比赛的结果完全是由订单决定。

Think of this as a knock out singles tennis tournament, where player abilities have a strict order and the outcome of a match is decided solely by that order.

在第一轮一半的人被消除。在下一轮的另一半等（有一些轮空可能）。

In the first round half the people are eliminated. In the next round another half etc (with some byes possible).

最后的赢家是决定最后一个，也是最后一轮。

Ultimately the winner is decided in the last and final round.

这可以被看作是一个树

树的每个节点都将成为该节点的孩子之间比赛的胜者。

Each node of the tree will be the winner of the match between the children of that node.

树叶的球员。第一轮的优胜者是叶子的父母等。

The leaves are the players. The winner of the first round are the parents of the leaves etc.

这是n个节点的完全二叉树。

This is a complete binary tree on n nodes.

现在跟随冠军的道路。有日志n与赢家发挥。现在考虑这些日志n个匹配的输家。第二个最好的一定是在那些最好的。

Now follow the path of the winner. There are log n matches the winner has played. Now consider the losers of those log n matches. The second best must be the best among those.

获奖者决定在N-1的比赛（你敲了每场一个）和LOGN之间的胜者决定在LOGN -1比赛。

The winner is decided in n-1 matches (you knock out one per match) and the winner among the logn is decided in logn -1 matches.

因此​​，你可以决定的最大和第二大的N + LOGN ​​- 2比较

Thus you can decide the largest and second largest in n+logn - 2 compares.

在事实上，它可以证明，这是最佳的。在最坏的情况下进行任何比较方案，获胜者将必须玩LOGN匹配

In fact, it can proven that this is optimal. In any comparison scheme in the worst case, the winner would have to play logn matches.

要证明假设点系统，其中一场比赛后，获胜者可以得到的输家之分。最初，所有每1点开始了。

To prove that assume a point system where after a match the winner gets the points of the loser. Initially all start out with 1 point each.

在结束最后的赢家有n个点。

At the end the final winner has n points.

现在给出的任何算法，它可以被布置成使玩家更多的点是永远的赢家。因为任何人的点至多双在那种情况下任何比赛，你至少需要数n个匹配的赢家最坏的情况下发挥。

Now given any algorithm, it could be arranged so that player with more points is always the winner. Since the points of any person at most double in any match in that scenario, you require at least log n matches played by the winner in the worst case.

这篇关于查找最大和第二大的N个数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！