algorithm - 随机快速排序 : probability of two elements comparison?

Question

我正在阅读 M.Mitzenmacher 和 E.Upfal 的“Probability and Computing”。我在理解如何计算两个元素的比较概率时遇到问题。

输入: 排序后的数字列表 (y1,y2,...,yN)。我们正在寻找枢轴元素(随机)。问题:比较两个元素yi 和yj (j>i) 的概率是多少？

答案(来自书本):如果在序列 (yi,yi+1,...,yj-) 的第一次抽取中选择 yi 或 yj 作为枢轴，则将比较 yi 和 yj 1,yj)。所以概率是:2/(j-i+1)。

我的问题是初始声明:例如，在第一次抽取时从整个列表中选择 yi 将导致与 yj 进行比较(反之亦然)，概率为 2/n。

因此，“反向”声明是正确的——(yi+1,...,yj-1) 元素都不能在 yi 或 yj 之前被选择，但“池”大小不固定(在第一次绘制时它肯定是 N，但在第二次绘制时它更小)。

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

Edit1:一些好心人完善了我的帖子，谢谢 :-)。

Edit2:列表最初是排序的。

Answer 1

Quicksort 的工作原理是将每个元素与主元进行比较:大于主元的元素放在主元的右侧，不大于主元的放在左侧(或者相反，如果你想要降序排序，它不会'没关系)。

在每一步中，枢轴都是从序列(yi, yi+1, ..., yj) 中选择的。这个序列有多少个元素？ j - i + 1(我想你打错了，它不可能是 y - i + 1)。

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

The problem for me is initial claim: for example, picking up yi in the first draw from the whole list will cause the comparison with yj (and vice-versa) and the probability is 2/n.

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

编辑:

再次阅读问题，我确实觉得它有点模棱两可。 在递归的第一步比较两个元素的概率确实如你所说的2/n，因为i和 j 为 1 和 n。 在未知递归步骤比较两个元素的概率就是我在上面解释的。