了解“中位数”algorithm

我想了解下面例子中的“中位数”algorithm：

我们有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 

1. 第一步是sorting每个组（在这种情况下，他们已经sorting）

2. 第二步recursion地找出中位数的“真实”中位数（ 50 45 40 35 30 25 20 15 10 ），即将该组合分为2组：

    50 25 45 20 40 15 35 10 30 

   整理这两个组

    30 10 35 15 40 20 45 25 50 

中位数是40和15（如果数字是偶数，我们取左中位数），所以返回值是15，但是中位数（ 50 45 40 35 30 25 20 15 10 ）的“真”中位数是30，而且有5个元素less于15个，远低于维基百科提到的45％的30％

所以T(n) <= T(n/5) + T(7n/10) + O(n)失败。

顺便说一下，在维基百科的例子中，我得到recursion结果为36.但是，真正的中位数是47。

所以，我认为在某些情况下，这个recursion可能不会返回中位数的真正中位数。 我想了解我的错误在哪里

Answer 1

问题在于你说find中位数的真正中位数的步骤。 在你的例子中，你有这些中位数：

 50 45 40 35 30 25 20 15 10 

这个数据集的真正的中位数是30，而不是15。你不会发现这个中位数的分组为五个块，并取这些中位数的中位数，而是recursion调用这个较小的组selectalgorithm。 你的逻辑错误是假设这个组的中位数是通过将上面的序列分成两个块来find的

 50 45 40 35 30 

和

 25 20 15 10 

然后find每个块的中位数。 相反，中位数algorithm会recursion地调用自己的完整数据集50 45 40 35 30 25 20 15 10 。 在内部，这会将组拆分成五个块并对它们进行sorting等，但是这样做是为了确定分区步骤的分区点，并且在这个分区步骤中，recursion调用将find中位数的真正中值，在这种情况下将是30.如果你使用30作为原始algorithm中的分割步骤的中位数，你确实得到了一个非常好的分裂根据需要。

希望这可以帮助！

Answer 2

这里是中位数algorithm的中间值的伪代码 （稍加修改，以适应您的例子）。 wikipedia中的伪代码无法描述selectIdx函数调用的内部工作方式。

我已经向代码添加了注释以供解释。

 // L is the array on which median of medians needs to be found. // k is the expected median position. Eg first select call might look like: // select (array, N/2), where 'array' is an array of numbers of length N select(L,k) { if (L has 5 or fewer elements) { sort L return the element in the kth position } partition L into subsets S[i] of five elements each (there will be n/5 subsets total). for (i = 1 to n/5) do x[i] = select(S[i],3) M = select({x[i]}, n/10) // The code to follow ensures that even if M turns out to be the // smallest/largest value in the array, we'll get the kth smallest // element in the array // Partition array into three groups based on their value as // compared to median M partition L into L1<M, L2=M, L3>M // Compare the expected median position k with length of first array L1 // Run recursive select over the array L1 if k is less than length // of array L1 if (k <= length(L1)) return select(L1,k) // Check if k falls in L3 array. Recurse accordingly else if (k > length(L1)+length(L2)) return select(L3,k-length(L1)-length(L2)) // Simply return M since k falls in L2 else return M } 

以你为例：

中位数函数的中位数将在45个元素的整个数组上调用，如（ k = 45/2 = 22 ）：

 median = select({48 49 50 51 52 43 44 45 46 47 38 39 40 41 42 33 34 35 36 37 28 29 30 31 32 23 24 25 26 27 18 19 20 21 22 13 14 15 16 17 8 9 10 53 54}, 45/2) 

1. 第一次调用M = select({x[i]}, n/10) ，array {x[i]}将包含以下数字： 50 45 40 35 30 20 15 10 。 在这个调用中， n = 45 ，因此select函数调用将是M = select({50 45 40 35 30 20 15 10}, 4)

2. 第二次调用M = select({x[i]}, n/10) ，array {x[i]}将包含以下数字： 40 20 。 在这个呼叫中， n = 9 ，因此呼叫将是M = select({40 20}, 0) 。 此select呼叫将返回并分配值M = 20 。

   现在，到了您有疑问的地步，我们现在将数组L划分为M = 20 ， k = 4 。

   记住arraysL在这里是： 50 45 40 35 30 20 15 10 。

   根据规则L1 < M ， L2 = M和L3 > M将arrays划分成L1, L2和L3 。 因此：
   L1: 10 15
L2: 20
L3: 30 35 40 45 50

   由于k = 4 ，它大于length(L1) + length(L2) = 3 。 因此，search将继续进行下面的recursion调用：
   return select(L3,k-length(L1)-length(L2))

   这意味着：
   return select({30 35 40 45 50}, 1)

   结果会返回30。 （因为L有5个或更less的元素，因此它将返回sorting数组中第k个第1个位置的元素，即30）。

现在，在45个元素的整个arrays上的第一个select函数调用中将接收到M = 30 ，并且将围绕M = 30分离arraysL的相同划分逻辑应用于最终得到中位数的中值。

唷！ 我希望我详细而清楚地解释中位数algorithm的中位数。