Geek Answers Handbook

The average number of intervals from entering 0..N

The question arose when considering "Find the missing K numbers in this set that should cover the question [0..N]."

The question author asked for CS answers instead of equations based answers, and his suggestion was to sort the input and then iterate over it to list the missing K numbers.

While it seems good to me, it also seems wasteful. Take an example:

  • N = 200
  • K = 2 (we will consider K <N)
  • missing items: 53, 75

A “sorted” set can be represented as:, [0, 52] U [54, 74] U [76, 200]which is more compact than listing all the values ​​of a set (and allows you to extract missing numbers in O (K) operations for comparison with O (N) if the set is sorted).

However, this is the end result, but during the construction the list of intervals can be much longer, since we feed the elements one at a time ...

So, we introduce another variable: let Ibe the number of elements in the set that we have so far brought into the structure. Then we can in the worst case have: min((N-K)/2, I)intervals (I think ...)

From which it follows that the number of intervals reached during the construction is the maximum encountered for I in [0..N] (N-K)/2, thus the worst case O(N).

However, I get the feeling that if the input is random, instead of being specially processed, we can get a much smaller border ... and, therefore, there is always such a difficult question:

How many intervals ... on average?

+5
1

, -, , - .

, , , :

S - . n - : n = |S|. max - : max = max(S). k - , : k = |{0,...,max} \ S|.

n S . O(n). , k, O(nlogn), O(n).

, n, k O(n) + O(nlogn) + O(n) = O(nlogn).

, S. ​​ ? ( ), . e? , :

  • , e
  • e, .
  • e+1, e-1, e
  • e+1, e-1 S, e
  • e-1, e+1 S, e
  • , e .

, , , O(logn). 4 5. , ( ). 3. 6. , , , O(logn), "" , O(logn).

k, . , <= n/2, O(n) .

, , n O(nlogn) + O(n) k , O(nlogn).

.

array max .

e, array[e] = true. , , .

, f, array[f] == false. O(max).

n k : O(n) + O(max). max = n + k, O(n + k).

, , , : , .

S -, S max. k, R, {0,...,max}. S S R.

O(n + k).

+1

More articles:


All Articles