我通过确定性位数的分析工作的假设下发现，输入被分为3个部分，而不是5，问题是它在哪里打破？

确定性值寻找算法：

选择（I，N）

除以n个元素到5组。 找到每个5元组的死记硬背的中间值。

递归选择中位数的X⎣n的/5⎦ 组中位数是支点。

绕枢轴X分区。令k =秩（X）

4，如果我= K，然后返回X

ELSEIF I＆LT;氏/ P>

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

别的递归选择第（i-k）次 在上部最小元素

我经历了算法的分析，笔者认为，步骤1和3将O（n），其中它只是只需要一定的时间找到5个元素中位数和第二步需要T（N / 5）的.so至少3/10元件被≤p和至少3/10的阵列的是≥磷，因此，第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。

一般在组五个可以说克= N / 5组和至少⌈g/2⌉ 对他们（这些群体的中间值≤P）至少有三个五行都≤页。所以元件≤p的总数目至少3⌈g/2⌉≥3N / 10。但在组3中我们可以得到所有的三个要素可能比P值。在这里我想该算法将打破！

难道我的想法正确的???

在一组3中，作为对于5的基团，大约一半的基团的人员在中位数元素小于-的中值中位数的，所以在这些团体可以舍弃元素低于其位数。在你的情况，（1,2,10），比11中位数少，这样你就可以放弃1和2。

在哪里，我认为事情分解为3组是在成本核算。 3（地板（地板（正/ 5）/ 2 - 2），该大致为3n / 10变为2（地板（地板（N / 3）/ 2 -2）左右，这大致N / 3这意味着。 7N / 10成为2π/ 3。地板（N / 5）变得楼（N / 3），这样反而7cn / 10 + 2 CN / 10 = 9cn / 10你会得到的只是2 CN / 3 + CN / 3 = CN，而不是T（n）的＆LT; = CN你将有东西在那里，你将不得不密切关注不涉及c中的条款，你最后可能会显示出它毕竟不是线性的。

看起来你实际上得到扔掉略多元素在递归的每个阶段，但递归除以3，没有5​​离开的工作量，这是不够的收支平衡。

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???

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.