Geek Answers Handbook

Worst case O (n) algorithm for k-selection

Besides the median median algorithm, is there any other way to make k-choice in the worst case O (n) time? Does median median make sense? I mean, is the performance advantage enough for practical purposes?

+5
source share
4 answers

There is another algorithm for calculating kth order statistics, based on the soft heap data structure , which is an option in the standard priority queue that allows you to "spoil" a certain number of priorities that it stores. The algorithm is described in more detail in a Wikipedia article, but the main idea is to use the soft heap efficiently (O (n) time), select a reference point for the separation function, which has a guarantee of good separation. In a sense, this is simply a modified version of the median median algorithm, which uses a (possibly) simpler approach to selecting a collapse element.

, , ( " Chazelle" ), , .

, , O (n), introselect. . quickselect, . , . Introselect , , . - O (n 2) , - . , , , - , , , , , quickselect. O (n).

, ( quickselect ), . ( "Introspective " ).

, !

+11

, , , N . STL (++), std::nth_element , O (n). , ++, , , .

++, nth_element .

+3

. , , . , , , .

, , , , , , , - .

+1

:

, , Quicksort Hoare. 9.3 " " CLRS. , , random_partition quicksort ( ):

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 .633 , ! , STL nth_permutation , .

0

More articles:


All Articles