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

Question

我正在研究确定性中值发现的分析,假设输入分为3个部分而不是5个,问题是它在哪里分解？

确定性中值发现算法:

SELECT(i,n)

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

2. 递归地选择⎣n/5⎦组中位数的中位数x作为支点.

3. 围绕枢轴x分区.设k = rank(x)

4.如果i = k则返回x

否则我<k

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

否则递归地选择上部的第(i-k)个最小元素

我对算法进行了分析,我相信第1步和第3步将采用O(n),只需要恒定的时间来找到5个元素的中位数,Step2需要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(大约3n/10的楼层(楼层(n/5)/ 2-2)变成2(楼层(楼层(n/3)/ 2 -2)左右,大致为n/3.这意味着7n/10变为2n/3. floor(n/5)变为floor(n/3),所以不是7cn/10 + 2cn/10 = 9cn/10你只得到2cn/3 + cn/3 = cn,而不是T(n)<= cn,你将需要仔细研究不涉及c的术语,最后你可能会发现它毕竟不是线性的.

看起来你实际上会在递归的每个阶段丢掉更多的元素,但是递归将剩下的工作量除以3而不是5,这还不足以实现收支平衡.