为什么中位数算法不能使用块大小 3？
我正在对确定性中值进行分析，假设输入分为 3 部分而不是 5 部分，问题是它在哪里分解？
确定性中值查找算法：
SELECT(i, n)
将 n 个元素分为 5 组。 死记硬背找出每个 5 元素组的中值。
递归选择⎣n/5⎦的中位数x 将中位数分组为枢轴。
围绕枢轴 x 进行分区。令 k =rank(x)
4.如果 i = k 则返回 x
，否则如果 i < k
然后递归选择第 i 个 下部的最小元素
否则递归选择第 (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。在这里我认为算法会崩溃！
我的想法正确吗？？？
I am Working through the analysis of deterministic median finding under the assumption that the input is divided into 3 parts rather than 5 and the question is Where does it break down?
the deterministic median finding algorithm:
SELECT(i, n)
Divide the n elements into groups of 5.
Find the median of each 5-element group by rote.Recursively SELECT the median x of the ⎣n/5⎦
group medians to be the pivot.Partition around the pivot x. Let k = rank(x)
4.if i = k then return x
elseif i < k
then recursively SELECT the ith
smallest element in the lower part
else recursively SELECT the (i–k)th
smallest element in the upper part
I went through the analysis of the algorithm and I believe that Step 1 and 3 will take O(n) where it just takes just constant time to find the median of 5 elements and Step2 takes T(n/5).so at least 3/10 of elements are ≤ p, and at least 3/10 of the array is ≥ p, therefore,Step 4 will T(7n/10) and will get the recurrence.
T(n) ≤ cn + T(n/5) + T(7n/10),
but when I divide the elements in goroup of 3, let say the 9 elements and I divided them in group such that:
{1,2,10} {4,11,14}, {15,20,22}
I got the medians 2,11,20 and the p=11.
in general in group of five lets say g = n/5 groups and at least ⌈g/2⌉
of them (those groups whose median is ≤ p) at least three of the five elements are ≤ p. so the total number of elements ≤ p is at least 3⌈g/2⌉ ≥ 3n/10. BUT in group of 3 we can get all the three elements might be LESS than p. and here I think the algorithm will break down !!
Did I get the idea correct???
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（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。 楼层（n/5） 变成 楼层（n/3），所以你不是 7cn/10 + 2cn/10 = 9cn/10为了得到 2cn/3 + cn/3 = cn，而不是 T(n) <= cn 你将不得不仔细查看不涉及 c 的项，你可能会最终表明它毕竟不是线性的。
看起来你实际上在递归的每个阶段都会丢弃更多的元素，但递归将剩余的工作量除以 3，而不是 5，这不是。足以收支平衡。
In a group of 3, as for the groups of 5, about half of the groups will have their median element less than the median-of-medians, so in those groups you can discard elements less than their median. In your case, (1,2,10) has its median less than 11, so you can discard 1 and 2.
Where I think things break down for groups of 3 is in the costing. 3(floor(floor(n/5)/2 - 2) which is roughly 3n/10 becomes 2(floor(floor(n/3)/2 -2) or so, which is roughly n/3. This means that 7n/10 becomes 2n/3. floor(n/5) becomes floor(n/3), so instead of 7cn/10 + 2cn/10 = 9cn/10 you are going to get just 2cn/3 + cn/3 = cn, and instead of T(n) <= cn you are going to have something where you will have to look closely at the terms that don't involve c, and you might end up showing that it is not linear after all.
It looks like you actually get to throw away slightly more elements at each stage of the recursion, but the recursion divides the amount of work left by 3, not 5, and this isn't enough to break even.