我正在阅读 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 - ɑ
- 1 - 2ɑ
- 2 - 2ɑ
我不确定如何回答这个问题。有什么想法吗?
最佳答案
让数组中有 N
个元素。如果选取的主元是数组中最小的 [Nα]
元素之一,则左分区的大小将小于 Nα
。同样,如果选择的主元是数组中最大的 [Nα]
元素之一,则右分区的大小将小于 Nα
。
因此,您可以选择 N - 2 * [Nα]
个元素,使两个分区的大小都大于或等于 Nα
。由于该算法随机选择一个枢轴,因此所有元素被选中的概率均等。
因此,得到这样的 split 的概率是 1 - 2α + O(1/N)
。
关于algorithm - 随机快速排序划分概率,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53312485/