是否有一种“锦标赛”算法可以找到第k大的元素？

Question

是否有一种“锦标赛”算法可以找到第k大的元素？

algorithmlanguage-agnosticselection

5

我知道我们可以使用“锦标赛”算法在大小为N的数组中找到第二大的元素，并在N+log(N)-2的时间内完成。现在我想知道是否可以使用类似的“锦标赛”方法找到第k大的元素。

我知道有一个O(N)的“选择”算法可以找到第k大的元素。它使用带有“好”枢轴的快速选择，在O(N)时间内可以找到。我们也可以在O(N)时间内从数组中构建一个堆，并从堆中检索第k个元素。

我想知道是否还有其他方法。

- Michael

2

http://en.wikipedia.org/wiki/Selection_algorithm 给出了一个相当不错的总结。 - user684934

使用堆排序的时间复杂度为O(n + k log n)，而不是O(n)。另外，我可以问一下你为什么要寻找其他方法吗？（这是作业吗？） - Saeed Amiri

@SaeedAmiri O(n + k log n) 等于 O(n) :) 这不是作业，只是我的好奇心。 - Michael

@Michael，不，它不是O(n)，如果k是常数，那么是的，但是例如如果k=n/2，它将是O(n logn)，远非您提到的线性O（如果它是O(n)，那么人们肯定不会发明选择算法）。 - Saeed Amiri

@SaeedAmiri 谢谢。你说得对，我现在明白了。 - Michael

如果您采用确定性版本的选择算法（枢轴被选为5个组的中位数），它也可以被制作成类似于锦标赛的形式，尽管这将是一棵相当复杂的树。 - Amit Prakash

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- MvG · Accepted Answer

我相信你可以将此算法转化为O(N log k)：遍历数组，并维护一个最小堆，该堆保存到目前为止遇到的最大的k个元素。因此，前k个元素直接进入堆中。每个后续元素将与堆顶进行比较，如果它更大，则堆顶将从堆中删除，并插入新元素，这是一个大小为k的堆的O(log k)操作。当算法完成时，序列长度至少为k，则堆顶将具有第k个最大元素，其余元素则保存在堆中。

这种方法的最坏情况性能不如中位数-of-medians O(n)解决方案，但易于实现，对于小规模的k而言效果相当不错，因此它可能非常适用于许多实际应用场景。