用于进行 k 选择的最坏情况 O(n) 算法

Question

除了中位数算法之外，还有其他方法可以在最坏情况 O(n) 时间内进行 k 选择吗？实施中位数是否有意义？我的意思是，性能优势对于实际用途来说是否足够好？

Answer 1

还有另一种基于软堆计算第k阶统计量的算法 数据结构，它是标准优先级队列的变体，允许“破坏”其存储的一定数量的优先级。该算法在维基百科文章中有更详细的描述，但基本思想是使用软堆有效地（O(n) 时间）为分区函数选择一个保证良好分割的主元。从某种意义上说，这只是中位数算法的修改版本，它使用（可以说）更直接的方法来选择主元元素。

软堆不是特别直观，但是本文中有对它们的很好的描述（“Chazelle 软堆的更简单实现和分析”），其中包括数据结构的正式描述和分析。

但是，如果您想要一个非常快的、最坏情况 O(n) 算法，请考虑考虑introselect。这个算法实际上非常聪明。它首先使用 快速选择算法，该算法会不智能地选择一个枢轴并使用它对数据进行分区。这在实践中非常快，但在最坏情况下表现不佳。 Introselect 通过跟踪跟踪其进度的内部计数器来修复此问题。如果算法看起来即将退化到 O(n²) 时间，它会切换算法并使用中位数之类的东西来确保最坏情况的保证。具体来说，它会监视每一步丢弃了多少数组，如果在丢弃一半输入之前发生了一些恒定数量的步骤，则算法会切换到中位数算法，以确保下一个主元之前是好的。然后使用快速选择重新启动。这保证了最坏情况下的 O(n) 时间。

该算法的优点是它对大多数输入都非常快（因为快速选择非常快），但具有很大的最坏情况行为。该算法的描述以及相关的排序算法 introsort 可以在 本文（“内省排序和选择算法”）。

希望这有帮助！

Answer 2

我认为当你的容器中有 N 百万个元素时，你应该真正测试它并找出性能如何。该算法已在 STL 库 (C++) 中实现，因为 std::nth_element 保证预期为 O(n)。因此，如果您使用 C++，您可以轻松地运行一些测试，看看性能是否足以满足您的需求。

一个值得注意的例外是 C++，它提供了模板化的 nth_element
保证预期线性时间的方法。

Answer 3

这取决于。如果你担心最坏的情况会意外发生，我不会打扰。随着数据增长到足以需要关注的程度，最坏的情况变得不可能发生，以至于几乎不值得防范。

如果您在客户端可以按最坏情况顺序提供数据以在服务器上执行拒绝服务的情况下进行选择，那么可能值得使用中位数的中位数来确保最坏情况顺序不会在任何程度上损害性能。

Answer 4

更新：

有一个线性时间算法，是快速排序的修改，由快速排序的发明者霍尔本人建议。
我建议参考CLRS书中的第9.3节“最坏情况线性时间的选择”。
这是简单的算法，假设我们有一个来自快速排序的方法random_partition（它使用随机主元进行分区）：

FindKth(array, l, u, k)
{
   int m = random_partition(array, l, u);
   if m == k : return array[k] /*we have found the kth element*/
   if m > k: return FindKth(array, l, m-1, k); /* we have found element > kth largest, concentrate on the left partition */
   else: return FindKth(array, m+1, u, k-m); /* find the k-m th element in the right partition */
}

您还可以参考 Donald Knuth 的 TAOCP Vol.3 排序和搜索 p.633
这种方法的优点在于，数组不需要完全排序！
我认为STL nth_permutation使用了这种技术，你可以参考注释部分。