Randomized quicksort partitioning probability

2019-08-21 09:42发布

I'm reading Algorithms Illuminated: Part 1, and problem 5.2 states:

Let ɑ be some constant, independent of the input array length n, strictly between 0 and 1/2. What is the probability that, with a randomly chosen pivot element, the Partition subroutine produces a split in which the size of both the resulting subproblems is at least ɑ times the size of the original array?

Answer choices are:

  1. ɑ
  2. 1 - ɑ
  3. 1 - 2ɑ
  4. 2 - 2ɑ

I'm not sure how to answer this question. Any ideas?

1条回答
放我归山
2楼-- · 2019-08-21 10:16

Let there be N elements in the array. If the picked pivot is one of the smallest [Nα] elements in the array, then the left partition's size will be less than . Similarly, if the picked pivot is one of the largest [Nα] elements in the array, the right partition's size will be less than .

Hence, there are N - 2 * [Nα] elements that you can pick such that both partitions have size greater than or equal to . Since the algorithm picks a pivot randomly, all elements have an equal probability of getting picked.

So, the probability of getting such a split is 1 - 2α + O(1 / N).

查看更多
登录 后发表回答