我读算法照明：第1部分和问题5.2状态：
让ɑ是一些恒定的，不依赖于输入数组长度n，严格介于0和1/2。 那是什么，与随机选择的枢轴元件，所述分区子例程产生的分裂，其中两个所得到的子问题的大小是原始数组的大小至少ɑ倍概率是多少？
正确答案的选项：
- ɑ
- 1 - ɑ
- 1 - 2ɑ
- 2 - 2ɑ
我不知道怎么回答这个问题。 有任何想法吗？
Answer 1:
要有N数组中的元素。 如果拾取枢轴是最小的一个[Nα]数组中的元素，则左分区的大小将小于Nα 。 类似地，如果所拾取枢轴是最大的一个[Nα]数组中的元素，合适的分区的大小将小于Nα 。
因此，存在N - 2 * [Nα]元素可以挑选，使得两个分区具有尺寸大于或等于Nα 。 由于算法挑选一个枢轴随机地，所有元件具有得到拾取的概率相同。
因此，获得这样的分裂的概率为1 - 2α + O(1 / N)
文章来源: Randomized quicksort partitioning probability
