基于快速排序分区的概率

Question

我遇到了这个问题：

设0<α<.5是某个常数（与输入数组长度n无关）。回想一下在课堂上讲解的快速排序算法中使用的Partition子例程。在随机选择主元素的情况下，Partition子例程产生子数组中较小的那个的大小≥α倍于原始数组大小的概率是多少？

Its answer is 1-2*α.

有人能解释一下这个答案是怎么得出来的吗？求帮助。

- POOJA GUPTA

---

由于它涉及更多理论性质，建议您将其发布在CS.SE上，可能会得到更好的回答。 - Sinkingpoint

@Quirliom：谢谢。我已经在cs.stackexchange上发布了这个问题。 - POOJA GUPTA

您应该说明这个问题来自于此 Coursera 课程的第三周，并且公开寻求答案是违反他们的荣誉代码的。换句话说，当您要求作业问题的解决方案时，请坦率地表明。 - Abhijit Sarkar

Answer 1

选择轴元素是随机的，具有均匀分布。

数组中有N个元素，我们将假定N很大（否则我们将得不到想要的答案）。

如果0≤α≤1，则小于轴元素的元素数量少于αN的概率为α。大于轴元素的元素数量少于αN的概率也相同。如果α≤1/2，则这两种情况是互斥的。

说较小的子数组长度≥αN，就是说上述两个条件都不满足，因此概率为1-2α。

- Beta

Answer 2

其他答案对我来说不太合适，这里提供另一种看法：

如果至少有两个子数组中的一个必须是，则可以推断出枢轴必须在位置。这显然是通过反证法得出的。如果枢轴，那么就会有一个小于的子数组。同样的道理，枢轴也必须是。任何更大的枢轴值都会在“右侧”产生比小的子数组。

这意味着 ，如下图所示：

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

我们计算事件的概率的方式是将组成结果的概率相加，即支点落在。

该总和表示为：

这很容易简化为：

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

- Matt Harrison

---

我认为1-2*alpha在这个例子中不起作用， 数组={1,2,3,4,5} alpha=0.3

---

根据公式，概率=1-2*0.3=0.4

---

然而，只有一个轴心点(3)，它可以分成两个大小为2的数组，因此最小值为2>=0.3*5=1.5，其余所有轴心点将具有更小的子数组大小为1，不满足条件>=1.5

---

因此，概率为1(只有一个轴心点3)/5(所有可能的轴心点)=0.2，这是否定了0.4。 - chebus

谢谢！我不是原帖作者，但这个答案对我来说真的很有意义，不像其他一些答案。 - BigBear

哇！谢谢，这是我读过的关于那个练习的最佳答案。 - Argonus

Answer 3

针对那些比较难理解这个问题的人，我再提供一种解决方法。

首先。 由于我们谈论的是“两个子数组中较小的一个”，那么它的长度应该小于原始数组元素数量的1/2（n为原始数组元素数量）。

其次。 如果0 < a < 0.5，则a * n也小于1/2 * n。因此，我们从现在开始讨论的是由0和1/2 * n所限制的两个随机选择的整数。

第三。 让我们想象一颗有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。

第四。 现在回到我们的问题上来。 "选择的数字"现在是a * 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。

- max.underthesun

Answer 4

数组长度为n。

对于较小的数组长度>=αn，枢轴应该大于αn个元素，同时枢轴应该小于αn个元素（否则较小的数组大小将小于所需大小）。

因此，在n个元素中，我们必须从(n-2α)n个元素中选择一个。

所需概率为n(1-2α)/n。

因此，1-2α。

- yashwanth

---

“pivot 应大于 αn 个元素。同时 pivot 应小于 αn 个元素”是什么意思？这两个似乎矛盾了。 - mc9

Answer 5

概率等于所需元素数量/总元素数量。 在本例中，((1-αn)-(αn))/n 由于α介于0和0.5之间，(1-α)必须大于α。因此二者之间包含的元素数量为， (1-α-α)n=(1-2α)n 因此，概率为， (1-2α)n/n=1-2α

- Swastik Udupa

Answer 6

另一种方法： 列出“更平衡”的选项：

αn + 1 to (1 - α)n - 1

αn + 2 to (1 - α)n - 2

...

αn + k to (1 - α)n - k

一共有k个。我们知道最平衡的是n / 2到n / 2，所以：

 αn + k = n / 2 => k = n(1/2 - α)

同样地，列出“不太平衡”的选项：

αn - 1 to (1 - α)n + 1

αn - 2 to (1 - α)n + 2

...

αn - m to (1 - α)n + m

总共有m个。我们知道最不平衡的是从0到n，因此：

αn - m = 0 => m = αn

由于所有这些选项发生的概率相等，我们可以使用概率的频率定义：

Pr{更平衡} =（更平衡的总数）/（所有选项的总数）=>

Pr{More balanced} = k / (k + m) = n(1/2 - α) / (n(1/2 - α) + αn) = 1 - 2α

- limido