随机快速排序划分概率

Question

我正在阅读算法说明:第一部分，问题5.2指出：

设ɑ是一个常数，与输入数组长度n无关，严格在0到1/2之间。对于随机选择的枢轴元素，PartitionSub例程产生一个分裂的概率是多少，其中两个子问题的大小至少是原始数组大小的ɑ倍？

答案选择如下：

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

我不知道怎么回答这个问题。有什么想法吗？

Answer 1

让数组中有N元素。如果选中的枢轴是数组中最小的[Nα]元素之一，则左分区的大小将小于Nα。类似地，如果选中的枢轴是数组中最大的[Nα]元素之一，则正确分区的大小将小于Nα。

因此，您可以选择N - 2 * [Nα]元素，这样两个分区的大小都大于或等于Nα。由于该算法随机选择一个支点，所有元素被选取的概率相等。

因此，得到这样一个分裂的概率是1 - 2α + O(1 / N)。