随机快速排序：两个元素进行比较的概率是多少？

Question

我正在阅读M.Mitzenmacher和E.Upfal的《概率与计算》。我在理解如何计算两个元素比较的概率方面遇到了问题。 输入：数字的排序列表(y1,y2,...,yN)。我们随机选择枢轴元素。问题：元素yi和yj(j>i)进行比较的概率是多少？ 答案(来自书中)：如果在从序列(yi,yi+1,...,yj-1,yj)的第一次抽样中选择yi或yj，则将比较yi和yj。因此，概率为：2/(j-i+1)。

对我来说，问题在于最初的声明：例如，在从整个列表的第一次抽样中选择yi将导致与yj进行比较(反之亦然)，概率为2/n。

因此，“相反”的说法是正确的——在yi或yj之前不能选择任何（yi+1，...，yj-1）元素，但“池”大小不是固定的（第一次绘制时它肯定是N，但第二次它会更小）。

有人能解释一下作者是如何得出这样简化的结论的吗？

编辑1：有些好心灵磨光了我的帖子，谢谢:-)。

编辑2：列表最初是排序的。

- bantu

Answer 1

快速排序通过将每个元素与枢轴进行比较来工作：大于枢轴的元素放置在枢轴右侧，不大于枢轴的元素放置在左侧（或者如果您想要降序排序，则相反无所谓）。

在每个步骤中，从序列(yi、yi+1、...、yj)中选择枢轴。这个序列有多少个元素？j - i + 1（我认为你打错了，它不能是 y - i + 1）。

因此，从该列表中选择两个特定元素的概率显然是2 / (j - i + 1)。

引起问题的是初始声明：例如，在第一次从整个列表中挑选yi时，将导致与yj进行比较（反之亦然），概率为2/n。

选择yi只会导致它仅与其他j-i个元素进行比较。您从哪里得到n？请记住，您的列表仅从yi到yj！

编辑：

再次阅读问题，我发现它有点含糊不清。确实，在递归的第一步中比较两个元素的概率确实是2/n，因为i和j分别为1和n。在未知递归步骤中比较两个元素的概率是我上面解释的。

- IVlad

---

谢谢您的评论，我已经更正了拼写错误并将信息添加到列表中 - 它最初是排序的。无论如何，我看到（在您的编辑中）您也发现了列表大小的问题，但最终结论是不正确的。您询问元素yi和yj，因此您甚至不能说在任何进一步的步骤中会有这样的序列yi..yj（例如，如果您选择yi + 1作为第一个枢轴，那么就不会有）。 - bantu

进一步的步骤并不重要。在每个步骤中，所选的枢轴将达到其最终位置，因此它在任何进一步的步骤中都不会起作用。 - IVlad

假设i>2。在第一步中，您选择了1，在第二步中选择了2。现在，在第三步中挑选i或j的概率是2/(N-3+1)，而不是2/(j-i+1)（正如您在编辑中最后一句中所写的）。更重要的是，这只是挑选这些元素的概率，而不是比较它们的概率，因为第三步的其他情况也会导致比较它们。每个步骤都确定概率，因此它们很重要。 - bantu

我想说的是，如果在当前递归步骤中选择了正确的枢轴，则进一步的步骤就不重要了。我感觉问题是要求在给定的递归步骤中选择正确的枢轴（yi或yj之一）的概率，对应于序列yi，yi + 1，...，yj。否则，你是对的，这个问题会更难。这确实是一个含糊不清的问题。 - IVlad

Answer 2

作者给出的答案是正确的，尽管我仍然不明白他们如何轻松快速地得出这个结论。

定义L=j-i+1。j和i的实际值并不重要，重要的是L。还可以用P(N,L)来表示从大小为N的有序数字序列中比较yi和yj元素的概率。

事实：

- P(N,2) = 1 - P(N,L) = 2/N+1/N * ( P(N-1,L)+P(N-2,L)+P(N-3,L)+...+P(L,L) )

这个总和看起来很丑，但经过两次测试后，P(N,L)可能等于2/L。让我们来验证一下：

- P(N,L=2) = 1 = 2/2 = 2/L - 假设P(N,L) = 2/L - P(N+1,L) = 2/(N+1) + 1/(N+1) * ( P(N,L) + ... P(L,L) ) = 2/(N+1) + (N-L+1)*1/(N+1)*2/L = 2/L

由于L=j-i+1，因此我们得到了2/(j-i+1)。

- bantu