了解"median of medians"算法

Question

我想了解以下示例中的"中位数"算法：

我们把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. 第一步是对每个组进行排序（在这种情况下，它们已经排序）

2. 第二步递归地确定中值（50 45 40 35 30 25 20 15 10）的"真"中值，即集合将分为两组：

   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个元素小于15，远小于维基百科中提到的45个元素的30%

因此CCD_ 3失败。

顺便说一下，在维基百科的例子中，我得到的递归结果是36。然而，真正的中位数是47。

所以，我认为在某些情况下，这种递归可能不会返回中值的真中值。我想知道我的错误在哪里。

Answer 1

问题在于您所说的找到中值的真正中值的步骤。在您的示例中，您有以下介质：

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作为中值作为分割步骤，那么确实可以根据需要获得非常好的分割。

希望这能有所帮助！

Answer 2

这是中位数算法的伪代码（根据您的示例稍作修改）。维基百科中的伪代码无法描述selectIdx函数调用的内部工作。

我在代码中添加了注释以进行解释。

// L is the array on which median of medians needs to be found.
// k is the expected median position. E.g. 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)时，数组{x[i]}将包含以下数字：50 45 40 35 30 20 15 10。在这个调用中，n = 45，因此选择函数调用将是M = select({50 45 40 35 30 20 15 10}, 4)

2. 第二次调用M = select({x[i]}, n/10)时，数组{x[i]}将包含以下数字：40 20。在该呼叫中，n = 9，因此该呼叫将是M = select({40 20}, 0)。此选择调用将返回并分配值M = 20。
   
   现在，到了您有疑问的地方，我们现在用k = 4围绕M = 20对数组L进行分区。
   
   记住这里的数组L是：50 45 40 35 30 20 15 10。
   
   阵列将根据规则L1 < M、L2 = M和L3 > M划分为L1, L2和L3。因此：
   L1: 10 15
L2: 20
T(n) <= T(n/5) + T(7n/10) + O(n)0
   
   由于k = 4，它大于length(L1) + length(L2) = 3。因此，现在将使用以下递归调用继续搜索：
   return select(L3,k-length(L1)-length(L2))
   
   其翻译为：
   return select({30 35 40 45 50}, 1)
   
   其结果将返回30。（由于L有5个或更少的元素，因此它将返回第k个元素，即排序数组中的第一个位置，即30）。

现在，M = 30将在45个元素的整个阵列上的第一个select函数调用中被接收，并且在M = 30周围分离阵列L的相同划分逻辑将应用于最终获得中值。

呜呜！我希望我足够详细和清楚地解释中位数算法。