最坏情况O（n）的算法做K

本文介绍了最坏情况O（n）的算法做K-选择的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

除了中位数的中位数算法，是否有任何其他的方式做K-选择在最坏情况下O（n）的时间？是否实施中位数的中位数意义;我的意思是，是的性能优势在实际应用不够好？

Apart from the median-of-medians algorithm, is there any other way to do k-selection in worst-case O(n) time? Does implementing median-of-medians make sense; I mean, is the performance advantage good enough for practical purposes ?

推荐答案

还有另一种算法计算的基础上的的软堆 数据结构，这是被允许的标准优先级队列中的变种的优先级将它存储腐败的一些数字。该算法进行更详细的维基百科文章中描述，但基本思想是使用软堆有效（O（n）的时间）选择一个枢轴为分区函数具有良好的分裂的保证。从某种意义上说，这简直是中位数的中位数的一种使用（可以说）更简单的方法来选择主元算法的修改版本。

There is another algorithm for computing kth order statistics based on the soft heap data structure, which is a variant on a standard priority queue that is allowed to "corrupt" some number of the priorities it stores. The algorithm is described in more detail on the Wikipedia article, but the basic idea is to use the soft heap to efficiently (O(n) time) pick a pivot for the partition function that has a guarantee of a good split. In a sense, this is simply a modified version of the median-of-medians algorithm that uses an (arguably) more straightforward approach to choosing the pivot element.

软堆是不是特别直观，但他们的pretty的很好的描述提供本文的，它包括一个正规的描述和分析，如果数据结构

Soft heaps are not particularly intuitive, but there is a pretty good description of them available in this paper, which includes a formal description and analysis if the data structure.

不过，如果你想的真快，最坏情况O（n）的算法，考虑寻找到的 introselect 。这种算法其实是相当辉煌。它通过使用开始关闭quickselect算法，该选取一个枢轴unintelligently并使用它来分割数据。这是在实践中非常快，但不好的最坏情况下的行为。 Introselect通过保持内部计数器跟踪其进展的轨迹修复此。如果算法永远看起来是关于降解为为O（n 2 ）时，它切换算法，并使用类似的东西中位数的位数以保证最坏情况下的保证。具体地，它的手表是如何阵列的多被废弃在每个步骤，并且如果发生的一些步骤恒定数目一半的输入被丢弃之前，算法切换到中位数的位数的算法，以确保下枢轴之前是好然后重新启动使用quickselect。这样可以保证最坏情况O（n）的时间。

However, if you want a really fast, worst-case O(n) algorithm, consider looking into introselect. This algorithm is actually quite brilliant. It starts off by using the quickselect algorithm, which picks a pivot unintelligently and uses it to partition the data. This is extremely fast in practice, but has bad worst-case behavior. Introselect fixes this by keeping track of an internal counter that tracks its progress. If the algorithm ever looks like it's about to degrade to O(n2) time, it switches algorithms and uses something like median-of-medians to ensure the worst-case guarantee. Specifically, it watches how much of the array is discarded at each step, and if some constant number of steps occur before half the input is discarded, the algorithm switches to the median-of-medians algorithm to ensure that the next pivot is good before then restarting using quickselect. This guarantees worst-case O(n) time.

该算法的优点是，它的速度非常快但对大多数输入（因为quickselect非常快），但具有很大的最坏情况下的行为。这种算法的描述，以及相关的排序算法introsort，可以发现的的本文

The advantage of this algorithm is that it's extremely fast on most inputs (since quickselect is very fast), but has great worst-case behavior. A description of this algorithm, along with the related sorting algorithm introsort, can be found in this paper.

希望这有助于！