基于快速分区的概率

Question

我遇到过这个问题:

令0 <α<.5为某个常数(与输入数组长度n无关).回想一下QuickSort算法采用的Partition子程序,如讲座中所述.通过随机选择的枢轴元素,分区子程序产生的分裂是多少,两个子阵列中较小的子阵列的大小是原始阵列大小的α倍？

Its answer is 1-2*?.

任何人都可以解释我这个答案是怎么来的？请帮助.

Answer 1

枢轴元素的选择是随机的,具有均匀分布.

数组中有N个元素,我们假设N很大(或者我们不会得到我们想要的答案).

如果0≤α≤1,则小于枢轴的元素数量小于αN的概率是α.大于枢轴的元素数量小于αN 的概率是相同的.如果α≤1/ 2,则这两种可能性是排他性的.

要说较小的子阵列的长度≥αN,就是说这些条件都不成立,因此概率为1-2α.

Answer 2

其他答案并没有完全符合我的意思，所以这是另一个问题：

如果 2 个子数组中的至少一个必须是 你可以推断出枢轴也必须就位 . 这是显而易见的矛盾。如果枢轴是 那么有一个小于 . 同理，枢轴也必须是. 枢轴的任何较大值将产生比 在右手侧”。

这意味着 ，如下图所示：

然后我们要计算的是该事件的概率（称为 A），即 .

我们计算事件概率的方法是对组成结果的概率求和，即枢轴落在 .

该总和表示为：

这很容易简化为：

通过一些取消，我们得到：

Answer 3

解决问题的另一种方法（对于那些像我一样难以理解的人）。

第一的。 既然我们在谈论“两个子数组中较小的那个”，那么它的长度小于 1/2 * n（n - 原始数组中的元素数）。

第二。 如果 0 < a < 0.5，则意味着 a * n 也小于 1/2 * n。因此，我们从现在开始谈论两个随机选择的整数，最低为 0，最高为 1/2 * n。

第三。 让我们想象一下骰子两边的数字从 1 到 6。让我们从 1 到 6 中选择一个数字，例如 4。现在掷骰子。每个数字都有 1/6 的概率成为该掷骰的结果。因此，对于事件“结果小于或等于 4”，我们的概率等于每个结果的概率之和。我们有数字 1、2、3 和 4。总共 p(x <= 4) = 4 * 1/6 = 4/6 = 2/3。所以事件“输出大于 4”的概率是 p(x > 4) = 1 - p(x <= 4) = 1 - 2/3 = 1/3。

第四。 让我们回到我们的问题。“选择的数字”现在是一个 * n。我们将用 0 到 (1/2 * n) 的数字掷骰子以获得 k - 最小子数组中的元素数。结果最高受 (a * n) 限制的概率等于从 0 到 (a * n) 的所有结果的概率之和。任何特定结果 k 的概率是 p(k) = 1 / (1/2 * n)。

因此 p(k <= a * n) = (a * n) * (1 / (1/2 * n)) = 2 * a。

由此我们可以很容易地得出结论，p(k > a * n) = 1 - p(k <= a * n) = 1 - 2 * a。