寻找第二大元素与比较的最小数量的数组 [英] Find the 2nd largest element in an array with minimum number of comparisons

问题描述

有关大小为N的数组，什么是比较的数量要求？

For an array of size N, what is the number of comparisons required?

推荐答案

最优算法采用N +登录N-2的比较。想想元素竞争对手和比赛是要对他们进行排名。

The optimal algorithm uses n+log n-2 comparisons. Think of elements as competitors, and a tournament is going to rank them.

首先，比较的元素，如在树

First, compare the elements, as in the tree

   |
  / \
 |   |
/ \ / \
x x x x

这需要n-1个比较，每个元素是参与最多的日志n次比较。你会发现最大的元素作为优胜者。

this takes n-1 comparisons and each element is involved in comparison at most log n times. You will find the largest element as the winner.

第二个最大的元素一定是输了一场比赛的获胜者（他不能输的比赛，以不同的元素），所以他的日志n个元素的赢家已经交手之一。您可以了解哪些人使用日志N - 1比较

The second largest element must have lost a match to the winner (he can't lose a match to a different element), so he's one of the log n elements the winner has played against. You can find which of them using log n - 1 comparisons.

的最优通过对手的说法证明。请参见 http://math.stackexchange.com/questions/1601 或<一href="http://compgeom.cs.uiuc.edu/~jeffe/teaching/497/02-selection.pdf">http://compgeom.cs.uiuc.edu/~jeffe/teaching/497/02-selection.pdf或 http://www.imada.sdu.dk/~jbj/DM19/lb06.pdf或<一href="https://www.utdallas.edu/~chandra/documents/6363/lbd.pdf">https://www.utdallas.edu/~chandra/documents/6363/lbd.pdf

The optimality is proved via adversary argument. See http://math.stackexchange.com/questions/1601 or http://compgeom.cs.uiuc.edu/~jeffe/teaching/497/02-selection.pdf or http://www.imada.sdu.dk/~jbj/DM19/lb06.pdf or https://www.utdallas.edu/~chandra/documents/6363/lbd.pdf

这篇关于寻找第二大元素与比较的最小数量的数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！