[Solved]: Finding the greatest $k$ numbers with a certainty of $p$

Problem Detail: 

Given $n \in \mathbb{N}$ pairwise distinct numbers. I want to do as few comparisons per number as possible - and every number should experience roughly the same amount of comparisons as another number - and find the greatest $k \leq n$ numbers, e.g. $k = \frac{n}{10}$. In order to minimise the number of comparisons per number, I allow an error, say I am okay if I know that the result is correct with only a probability of $p$.

I study mathematics and only had a very shallow introduction to algorithms so far, and the only relevant algorithms we discussed would be sorting algorithms. QuickSort comes to mind, but firstly I am not sure how I would implement my "tolerance of an error" and secondly, I think the fact that I only need the greatest $k$ numbers and I don't want to sort them, there might be more efficient algorithms.

Any basic approach would be a great help already, I'll gladly do the maths on my own.

Thanks in advance for any help.

Asked By : Huy

Answered By : A.Schulz

I propose the following algorithm. You take some random element $p$ of your input as pivot element for $k=n/10$. Next, you scan through all your data and split it into a list of elements $\le p$ and a list with elements $>p$.

Case 1: The list with the larger elements contains more then $k$ elements. Then take this list and repeat.
Case 2: The list with the larger elements contains less than $k$ elements, say $m$. The repeat with the other list, but set $k=k-m$.
Case 3: Otherwise you are done.

This is very easy to implement and should find the solution quickly. (You said you want to do the math by yourself ;) )

Remark: There is a classic $O(n)$ algorithm for this. You can determine the $k$-th biggest element in $O(n)$ by the algorithm of Blum et al. and then use this element as pivot. However, I think the the constant in the $O(n)$ makes this variant slower then the above solution. Especially if you are fine with an imprecise solution.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7359

3.2K people like this

 Download Related Notes/Documents