我正在阅读 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:列表最初是排序的。
最佳答案
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
。 在未知递归步骤比较两个元素的概率就是我在上面解释的。
关于algorithm - 随机快速排序 : probability of two elements comparison?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2750726/