5

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

4

4 回答 4

12

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

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

但是，如果您想要一个非常快速、最坏情况的 O(n) 算法，请考虑研究introselect。这个算法实际上非常出色。它首先使用快速选择算法，该算法在不智能的情况下选择一个枢轴并使用它来划分数据。这在实践中非常快，但在最坏情况下的行为很糟糕。Introselect 通过跟踪跟踪其进度的内部计数器来解决此问题。如果算法看起来即将降级到 O(n 2) 时间，它会切换算法并使用中位数之类的东西来确保最坏情况的保证。具体来说，它观察每一步丢弃了多少数组，如果在丢弃一半输入之前发生了一些恒定数量的步骤，则算法切换到中位数算法以确保下一个枢轴之前是好的然后使用快速选择重新启动。这保证了最坏情况的 O(n) 时间。

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

希望这可以帮助！

于 2011-09-09T18:34:47.670 回答
3

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

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

于 2011-09-09T08:27:24.567 回答
1

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

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

于 2011-09-09T08:38:20.737 回答
0

更新：

有一种线性时间算法，一种对快速排序的修改，由快速排序的发明者霍尔本人提出。我建议参考 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使用了这种技术，您可以参考注释部分。

于 2011-09-09T08:38:29.490 回答