在随机化Quicksort中比较两个元素的概率

Question

我在随机快速分析的特定部分中具有问题。

根据随机的快速排序算法，从给定的子集中选出从随机索引调用的子集，而不是每次选择特定索引。

现在假设我们给出了一系列大小说 $ n $ 到我们的随机Quicksort算法。

现在我请求看看下面给出的文本中的LEMMA-7.1的证明。现在我们已经给了我们的算法数组，这可以是元素的任何置换，而是在段落之后，刚刚在 $ lemma-7.1 $ 。

为什么作者考虑在执行分析时考虑输入数组的排序实例？

此外，如果在公式中查看文本 $（7.2）$ ，那里有证据他们的逻辑找到 $ z_i $ 应在我们的算法中与 $ z_j $ 进行比较。现在，他们正在考虑子集{ $ z_i $ ，...， $ z_j $ }。不是这种比较 $ z_i $ ， $ z_j $ 获取太具体了，如果我们认为这一点特定子集？我的意思是说我们正在使用随机方法，并且可以使用更广泛的外观来导出比较的概率，例如所有可能的情况差的置换。

我们正在使用特定子集，并且太排序并不令人信服我们如何为我们的算法获得正确的概率...

     {z1,z2,...,zn} zi being the ith minimum element
            ^
            |
            ----------------------------------------------------
                                                                |                           
    --P(Zi is compared with Zj)                                 |
   |                                                            |
   |                                                            |
   |-----> We are considering                                   |
   |        Zij = {Zi,Zi+1,...,Zj} which is a subset of --------
   |
   |------ Aren't we considering a very specific case??

.

和 $ 1 /（j-i + 1）$ - >-> total no。元素在 子集也是固定的 特定 $ i $ 和 $ j $

在考虑 $ z_i $ ， $ z_j $ ，子集中的概率两个元素在那里，要分区可以是任何（即，由任何可能的元素组成）和任何大小（不仅仅是 $ j-i + 1 $ ）...

可能是随机化条件实际上是占用的一切 帐户，但我没有得到它。请你能解释一下他们使用的逻辑，以找到所述概率，并请说服我正确地找到了比较的概率。

参考我附上了算法的相应页面第3 red-clrs

Answer 1

一个非常简单的证据：我声称如果存在x和y之间值的d整数，并且阵列中存在n≥2元素，则比较x和y的概率是2 /（d + 2 ），独立于n。

识别通过诱导：如果n= 2则清楚d= 0，所以索赔是x和y与概率2 /（0 + 2）= 1.这也明显正确，因为x和y必须明确正确比较。

现在让n≥3.对于第一个分区，我们随机选择枢轴。将每个阵列元素与枢轴进行比较，并且没有其他比较。因此，如果通过巧合，我们选择x或y作为枢轴，x和y将进行比较。这是2 / n的概率。如果通过巧合，我们选择一个具有x和y之间值的d元素之一，然后分区将x移动到一个分区，y到另一个分区，因此它们永远不会比较。如果我们选择其他一个N - D - 2元素之一，则X和Y最终在相同的分区中，并且通过感应与概率2 /（d + 2）进行比较。

因此，比较x和y的概率是

2 / n + (n - d - 2) / n * 2 / (d + 2) = 

2 * (d + 2) / (n * (d + 2)) + 2 * (n - d - 2) / (n * (d + 2)) =

(d + 2 + n - d - 2) * 2 / (n * (d + 2)) =

2 * n / (n * (d + 2)) = 

2 / (d + 2) qed.

.

当然是与yuval的结果相同，因为| j - i |= D + 1。随机化使分析很容易 - 如果我们例如说“如果n> 5然后随机挑选5个元素并选择那些5的中位数”，则分析将更复杂。

ps。纸上的证明更容易：当您分区数组时， $ x_i $ 和 $ x_j $ 保持在相同的子分区，直到使用具有I <= Pivot <= j的枢轴。如果该枢轴是i或j，那么 $ x_i $ 和 $ x_j $ ，否则它们不是比较的。所以机会是2 /（ABS（J-I）+ 1）。

Answer 2

证明的想法是计算，对于任何两个元素 $ x，y $ 在阵列中，它们在算法中比较了它们的概率。这种概率可能取决于整个阵列。但是，事实证明，您只能给出 $ x，y $ 的顺序统计，即它们在排序阵列中的相对顺序。如果您知道 $ x $ 是 $ i $ 数组中的最小元素， $ y $ 是 $ j $ th最小的元素在数组中，然后 $ x，y $ $ \ frac {2} {| | ji | +1} $ 。

这不是一个特例 - 每个元素 $ x $ 在数组中是 $ i $ th最小的元素，对于 $ i $ 的一些值。这只是允许我们计算 $ x $ 和 $ y $ 的概率的相关信息比较。