理解与QUOT;中位数＆QUOT的中位数;算法中位数、算法、QUOT
您好我想了解的算法在下面的示例中位数中位数：
因此，我们有45不同数字分为9组5个元件。
48 43 38 33 28 23 18 13 8
49 44 39 34 29 24 19 14 9
50 45 40 35 30 25 20 15 10
51 46 41 36 31 26 21 16 53
52 47 42 37 32 27 22 17 54
的第一步是排序各组（在这种情况下，他们已经排序）
第二步递归，科幻ND中位数的真值（ 50 45 40 35 30 25 20 15 10 ），即一组将分成2组：
50 25
45 20
40 15
35 10
三十
排序这2组
30 10
35 15
40 20
45 25
50
中位数是40和15的情况下（数字甚至我们就把左正中）
所以返回的值是15但中位数的真值（ 50 45 40 35 30 25 20 15 10 ）是30，而且有5个元素小于15，是45远小于30％，这都提到了wikipedia
等 T（n）的＆LT; = T（N / 5）+ T（7N / 10）+ O（N）失败
通过在维基百科的例子的方式，我得到递归36的结果，但真正的中位数为47。
所以，我认为在某些情况下，这递归可能不会返回中位数真值。我想知道哪里是我的错误。
解决方案现在的问题是在你说找中位数的真实值的步骤。在你的榜样，你有这些位数：
50 45 40 35 30 25 20 15 10
这组数据的真实值是30，不是15。你不觉得这位数由分裂组织成五个街区，并采取这些中位数的中位数，而是通过递归调用这个较小的选择算法组。在你的逻辑错误是假设这组的中位数是通过把上述顺序分成两个区块发现
50 45 40 35 30
和
25 20 15 10
然后找出每个块的中位数。相反，中位数的中位数算法将递归调用本身上的完整的数据集 50 45 40 35 30 25 20 15 10 。在内部，这将集团拆分成五个街区和排序，等等，但它这样做，以确定分区点分区步骤，它是在这个分区步骤中的递归调用会发现中位数的真实位数，在这种情况下将是30。如果使用30作为位数作为在原始算法的分区时，您确实得到了很好的分裂为必需的。
希望这有助于！
Hi I want to understand "median of medians" algorithm on the following example:
So we have 45 distinct numbers divided to 9 group with 5 elements.
48 43 38 33 28 23 18 13 8
49 44 39 34 29 24 19 14 9
50 45 40 35 30 25 20 15 10
51 46 41 36 31 26 21 16 53
52 47 42 37 32 27 22 17 54
The first step is sorting every group (in this case they are already sorted)
Second step recursively, find the "true" median of the medians (50 45 40 35 30 25 20 15 10) i.e. the set will be divided into 2 groups:
50 25
45 20
40 15
35 10
30
sorting this 2 groups
30 10
35 15
40 20
45 25
50
the medians is 40 and 15 (in case the numbers are even we took left median)
so the returned value is 15 however "true" median of medians (50 45 40 35 30 25 20 15 10) is 30, moreover there are 5 elements less then 15 which are much less than 30% of 45 which are mentioned in wikipedia
and so T(n) <= T(n/5) + T(7n/10) + O(n) fails.
By the way in wikipedia's example I get result of recursion 36 however the true median is 47.
So I think in some cases this recursion may not return true median of medians. I want to understand where is my mistake.
解决方案The problem is in the step where you say to find the true median of the medians. In your example, you had these medians:
50 45 40 35 30 25 20 15 10
The true median of this data set is 30, not 15. You don't find this median by splitting the groups into blocks of five and taking the median of those medians, but instead by recursively calling the selection algorithm on this smaller group. The error in your logic is assuming that median of this group is found by splitting the above sequence into two blocks
50 45 40 35 30
and
25 20 15 10
then finding the median of each block. Instead, the median-of-medians algorithm will recursively call itself on the complete data set 50 45 40 35 30 25 20 15 10. Internally, this will split the group into blocks of five and sort them, etc., but it does so to determine the partition point for the partitioning step, and it's in this partitioning step that the recursive call will find the true median of the medians, which in this case will be 30. If you use 30 as the median as the partitioning step in the original algorithm, you do indeed get a very good split as required.
Hope this helps!
