algorithm - 随机快速排序划分概率

Question

我正在阅读 Algorithms Illuminated: Part 1 ，问题 5.2 指出:

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?

答案选择是:

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

我不确定如何回答这个问题。有什么想法吗？

Answer 1

让数组中有 N 个元素。如果选取的主元是数组中最小的 [Nα] 元素之一，则左分区的大小将小于 Nα。同样，如果选择的主元是数组中最大的 [Nα] 元素之一，则右分区的大小将小于 Nα。

因此，您可以选择 N - 2 * [Nα] 个元素，使两个分区的大小都大于或等于 Nα。由于该算法随机选择一个枢轴，因此所有元素被选中的概率均等。

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