A fast algorithm to retrieve M distinct random values from an array of N values

Kaiyakha 0
Viewed 50

Recently I was offered to solve the following task (with C++).

Write a function which retrieves M distinct random values from N values.

Prerequisites:

  • the input array of N values is not necessarily sorted;
  • the input array of N values may contain duplicates.

The thing which made me ask for a solution is that I was said that it is possible to implement the algorithm which would have complexity O(M). To me this sounds insane and I haven't managed to find anything at least close to O(M).

Is it even possible to write the algorithm with such small complexity? If no, what complexity can I achieve at all? I would also like to see examples (not necessarily with C++).

time-complexity algorithm
1 Answers

As @Marat pointed out, this is impossible in general. The worst case is O(N).

If we want all subsets of M elements to be equally likely, you can do it in average time O(N) by simply keeping a hash of seen values, and then passing them as we first see them into a reservoir sampling algorithm. (Note, in practice hashes operate in O(1) time, but their theoretical worst case is O(N).)

If we don't care about equally likely, we can stop when you get M elements. The probability of including an element will be directly correlated with its frequency. This is on average a O(N) algorithm. But if we stipulate that the most common element is O(K) then this should finish in time O(K*M). Alternately if we have Omega(N) distinct values (Omega is the lower bound version of big-O), then this will finish in average time O(M).

The last requires explanation. If there are N0 distinct values, then there are two cases. If M < 2 * N0 then the expected waiting time to the next new value is never more than N0 / (2*N) (that's a bound on the waiting time for the very last after we've taken the first M-1). But otherwise we know that M = Omega(N) and we already know that we can examine the whole set in time O(N) = O(M). Either way we get our desired average time bound.

btilly0
Related