ban*_*ntu 8 algorithm probability quicksort
我正在阅读M.Mitzenmacher和E.Upfal的" 概率与计算 ".我在理解如何计算两个元素的比较概率时遇到问题.
输入:数字的排序列表(y1,y2,...,yN).我们正在寻找枢轴元素(随机).问题:两个元素yi和yj(j> i)的概率是多少？
答案(来自书): yi和yj将被比较,如果yi或yj将被选为第一次从序列中绘制的枢轴(yi,yi + 1,...,yj-1,yj).所以可能性是:2 /(j-i + 1).
对我来说问题是最初的主张:例如,在整个列表的第一次抽奖中拾取yi将导致与yj的比较(反之亦然),概率为2/n.
因此,相反"反向"声明是正确的 - 在yi或yj之前不能选择(yi + 1,...,yj-1)元素,但"池"大小不固定(在第一次绘制中)它肯定是N,但在第二个它更小).
有人可以解释作者如何提出这样一个简化的结论吗？
Edit1:一些好心灵打磨了我的帖子,谢谢:-).
Edit2:列表最初排序.
快速排序的工作原理是将每个元素与枢轴进行比较：那些大于枢轴的元素放置在枢轴的右侧，而那些不大于枢轴的则放置在左侧（或者相反，如果您想要降序排序，也没关系） 。
在每一步中，枢轴都是从序列中选择的(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。在未知的递归步骤中比较两个元素的概率就是我上面解释的。
作者给出的答案是正确的，尽管我仍然不明白他们是如何轻松快速地得出结论的。
让 表示为 L=j-i+1。j 和 i 的实际值在这里并不重要，重要的是 L。还用 P(N,L) 表示从大小为 N 的有序数字序列中比较 yi 和 yj 元素的概率。
事实：
这个总和看起来很难看，但经过两次测试后发现 P(N,L) 可能等于 2/L。让我们来看看：
由于 L=j-i+1，我们得到 2/(j-i+1)。