随机快速排序划分概率 [英] Randomized quicksort partitioning probability

问题描述

我正在阅读说明的算法：第1部分和问题5.2指出：

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

让ɑ是一些常数，与输入数组长度n无关，
严格介于0和1/2。使用
随机选择的枢轴元素，Partition子例程产生
拆分的概率是多少，因此两个子问题的大小至少为
ɑ乘以原始大小数组？

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ɑ

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

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

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

推荐答案

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

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 Nα. Similarly, if the picked pivot is one of the largest [Nα] elements in the array, the right partition's size will be less than Nα.

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

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

因此，进行此类拆分的概率为 1 -2α+ O（1 / N）。

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

这篇关于随机快速排序划分概率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！