我在读M.Mitzenmacher和E.Upfal的《AA>》。我在理解如何计算两个元素的比较概率时遇到了问题。
输入：数字的排序列表（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）元素，但是“pool”的大小不是固定的（在第一次绘制中肯定是n，但在第二次绘制时它更小）。
有人能解释一下作者是怎么得出这么简单的结论的吗？
伊迪丝1：一些善良的灵魂擦亮了我的帖子，谢谢。
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。在一个未知的递归步骤中比较两个元素的概率就是我上面解释的。