随机选择

Question

随机选择算法如下：

输入：一个数组$ a $ a $ n $（不同，简单）数字和[n] $中的数字$ k

输出：$ a $的“排名$ k $ element”（即，如果$ a $排序，则位置$ k $）

方法：

• 如果$ a $中有一个元素，请返回
• 随机选择一个元素$ p $（“枢轴”）
• 计算$ l = {a in A：a <p } $和$ r = {a in A：a> p } $ in：a <p } $
• 如果$ | l | ge k $，返回$ l $的等级$ k $ element。
• 否则，返回等级$ k - | l | $ r $的$ element

我被问到以下问题：

假设$ k = n/2 $，所以您正在寻找中位数，让$ alpha in（1/2,1）$成为一个常数。在第一个递归调用中，包含中位数最多尺寸的集合的概率是什么？

有人告诉我，答案为$ 2 alpha -1 $，其理由为“选定的枢轴应躺在$ 1- alpha $和$ alpha $ times the Original Array”之间。

为什么？作为$ alpha in（0.5，1）$，无论选择什么元素，枢轴要么大或小于原始元素的一半以上。中位数总是在于较大的子阵列，因为分区子阵列中的元素始终小于枢轴。

如果枢轴位于原始数组的前半部分（不到一半），则中位数肯定会在第二个较大的半部分，因为一旦找到中位数，它必须位于阵列的中间位置，并且如上所述，枢轴之前的所有内容都较小。

如果枢轴位于原始阵列的后半部分（超过一半的元素），则中位数肯定会出于相同的原因，而在枢轴之前的所有内容都被认为较小。

例子：

3 4 5 8 7 9 2 1 6 10

中位数为5。

假设所选的枢轴为2。因此，在第一次迭代后，它变成：

1 2 ....更大的零件....

仅有的 1 和 2 在第一次迭代后被交换。数字5（中位数）仍在前半部分（涉及枢轴2）。关键是，中位数总是落在更大的一半上，它如何有机会留在较小的子阵列中？

Answer 1

假设您的数组有$ n $元素。如您所指出的那样，中位数总是在第一个分区之后的较大部分。如果较小的零件的大小至少$（1- alpha）n $，则较大的部分最多具有$ alpha n $。当您选择不是最小或最大的$（1- alpha）n $元素之一的枢轴时，就会发生这种情况。因为$ alpha> 1/2 $，您知道这些是不相交的集，因此击中一个坏枢轴之一的概率仅为$ 2-2 alpha $，而$ 1-2 + 2 2 alpha = 2 alpha -1 -1 $。