以最少的比较次数查找数组中的第二大元素 [英] 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+log 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.

第二大元素必须输给获胜者(他不能输给其他元素)，所以他是获胜者对抗的 log n 个元素之一.您可以使用 log 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.

最优性是通过对手的论点证明的.请参阅 https://math.stackexchange.com/questions/1601 或 http://compgeom.cs.uiuc.edu/~jeffe/teaching/497/02-selection.pdf 或 http://www.imada.sdu.dk/~jbj/DM19/lb06.pdf 或 https://www.utdallas.edu/~chandra/documents/6363/lbd.pdf

The optimality is proved via adversary argument. See https://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屋！