algorithm - 为什么中位数算法不能使用 block 大小 3？

Question

我正在假设输入分为 3 部分而不是 5 部分，并且问题是它在哪里分解？

确定性中值查找算法:

选择(我，n)

1. 将 n 个元素分成 5 组。 死记硬背地找出每个 5 元素组的中位数。

2. 递归地选择⎣n/5⎦的中位数x 将中位数分组为枢轴。

3. 围绕枢轴 x 进行分区。让 k = rank(x)

4.if i = k then return x

否则我 < k

然后递归地选择第i个 下部最小元素

else 递归地选择第 (i–k) 个 上部最小元素

我对算法进行了分析，我相信第 1 步和第 3 步将花费 O(n)，其中只需要常数时间来找到 5 个元素的中值，而第 2 步需要 T(n/5)。所以至少 3/10 的元素 ≤ p，并且至少 3/10 的数组 ≥ p，因此，第 4 步将 T(7n/10) 并得到递归。 T(n) ≤ cn + T(n/5) + T(7n/10), 但是当我将元素分成 3 个 goroup 时，比如说 9 个元素，我将它们分成一组:

{1,2,10} {4,11,14}, {15,20,22}

我得到中位数 2,11,20 和 p=11。

一般来说，在五人一组中，假设 g = n/5 组，并且至少 ⌈g/2⌉ 其中(中位数≤p的那些组)五个元素中至少有三个≤p。所以 ≤ p 的元素总数至少为 3⌈g/2⌉ ≥ 3n/10。但是在 3 组中，我们可以得到所有三个元素可能都小于 p。在这里我认为算法会崩溃!!

我的想法正确吗？？？

Answer 1

在 3 人一组中，对于 5 人一组，大约一半的组的中值元素将小于中位数的中位数，因此在这些组中，您可以丢弃小于中位数的元素。在您的例子中，(1,2,10) 的中位数小于 11，因此您可以丢弃 1 和 2。

我认为 3 人一组的问题在于成本核算。 3(floor(floor(n/5)/2 - 2) 大约是 3n/10 变成 2(floor(floor(n/3)/2 -2) 左右，大约是 n/3。这意味着7n/10 变成 2n/3。floor(n/5) 变成 floor(n/3)，所以你将得到 2cn/3 + cn/3 = 而不是 7cn/10 + 2cn/10 = 9cn/10 cn，而不是 T(n) <= cn，您将不得不仔细查看不涉及 c 的项，并且最终可能会表明它毕竟不是线性的。

看起来您实际上可以在递归的每个阶段丢弃更多的元素，但是递归将剩余的工作量除以 3，而不是 5，这不足以实现收支平衡。