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

Question

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

algorithmselectionbig-omedian-of-medians

5

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

- Harman

首先排序，然后简单地选择第k个元素的时间复杂度仅为O(n log n)，而且有快速实现，因此是否值得使用更复杂的O(n)算法取决于具体细节，例如n的值。此外，不要忘记使用随机枢轴的快速选择算法，其期望时间复杂度为O(n)。 - ShreevatsaR

4个回答

3

我认为你应该真正地测试一下，看看当容器中有N百万个元素时，它的性能如何。这个算法已经在STL库（C++）中实现了，std::nth_element保证期望的时间复杂度是O(n)。因此，如果你使用C++，你可以轻松地运行一些测试，看看性能是否足够好来满足你的需求。

另外值得注意的是，C++提供了一个模板化的nth_element方法，保证期望的时间复杂度是线性的。

- Tony The Lion

很高兴知道，事实上我确实使用C++。 - Harman

1

我可能错了，但上面的文本不是说算法必须在预期 O(n) 时间内运行，而不是在最坏情况下的 O(n) 时间吗？ - templatetypedef

如果我过于挑剔，我很抱歉，但这个回答似乎仍然没有回答提问者的问题，即寻找更好的最坏情况下O(n)选择算法？ - templatetypedef

1

这要看情况。如果你担心最坏情况会意外发生，那就不必费心了。随着数据越来越大，最坏情况变得如此不太可能，以至于不值得防范。

如果你在选择时处于客户端可能按最坏情况顺序提供数据以对你的服务器进行拒绝服务攻击的情况下，那么使用中位数算法来确保最坏情况不会对性能造成重大影响可能是值得的。

- Jerry Coffin

0

更新：

有一种线性时间算法，是快速排序的发明者Hoare本人提出的修改版。我建议参考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 Sorting and Searching p.633 这种方法的美妙之处在于，数组不需要完全排序！我认为STL nth_permutation使用了这种技术，您可以参考注释部分。

- vine'th

1

这是QuickSelect，只有在选择随机基准时才期望线性时间，但最坏情况下为二次时间。 - ShreevatsaR

是的，你说得对；CLRS书使用随机分割方案，确保线性运行时间，你可以参考上面提到的章节。 - vine'th

1

即使随机选择枢轴也不能保证线性时间。它只是说在期望上行为是线性的。使用此算法绝对可以降级为O(n^2)。 - templatetypedef

在随机枢轴的情况下，O(n^2)的退化概率非常小，大约是10^-8左右，请参阅Knuth的TAOCP Vol.3 p.122以获取Knuth的数学分析。我发现他的数学很难理解 :) Knuth简单地说：“即使是稍微随机选择的q也应该是安全的。” 我相信STL的nth_permutation使用相同的算法，可以从注释部分看出。甚至他们都使用“平均线性”前缀。 - vine'th

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

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

- templatetypedef · Accepted Answer

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

软堆并不特别直观，但这篇论文（“Chazelle软堆的简单实现和分析”）中有一个相当好的描述，包括数据结构的正式描述和分析。

然而，如果你需要一个真正快速的最坏情况O(n)算法，请考虑研究 introselect。这个算法实际上非常聪明。它首先使用快速选择算法来选择一个无法理解的中轴点并将其用于数据分区。实践中这非常快，但最坏情况下表现不佳。通过跟踪内部计数器以跟踪进度，introselect修复了这个问题。如果算法即将降级为O(n²)时间，它会切换算法并使用类似中位数之类的算法来确保最坏情况保证。具体来说，它观察每个步骤丢弃了多少数组元素，如果在一半的输入被丢弃之前发生了某个常数次步骤，则算法切换到中位数之类的算法以确保接下来的中轴点是好的，然后重新开始使用快速选择。这保证了最坏情况O(n)时间。

该算法的优点是，在大多数输入上非常快速（因为快速选择非常快），但最坏情况下表现良好。关于此算法以及相关的排序算法introsort的描述可以在这篇论文("Introspective Sorting and Selection Algorithms")中找到。

希望这可以帮助你！