63

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

我们有 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）的“真实”中位数，即集合将分为 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 个小于 15 的元素远小于 30维基百科中提到的 45 个中的百分比

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

顺便说一句，在 Wikipedia 示例中，我得到的递归结果为 36。但是，真正的中位数是 47。

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

4

2 回答 2

37

问题在于您说要找到中位数的真实中位数的步骤。在您的示例中，您有以下中位数：

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 作为中值作为分割步骤，则确实得到了非常好的分割。

希望这可以帮助！

于 2012-02-28T20:31:17.793 回答
36

这是中位数算法的伪代码（稍作修改以适合您的示例）。维基百科中的伪代码未能描述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 个元素的整个数组中调用，例如 (with 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). 这个 select 调用将返回并赋值M = 20。

    现在，到了你有疑问的地方，我们L现在M = 20用k = 4.

    记住L这里的数组是：50 45 40 35 30 20 15 10.

    数组将根据规则划分为,L1, L2和。因此： 因为，它大于。因此，现在将通过以下递归调用继续搜索： 转换为： L3L1 < ML2 = ML3 > M
    L1: 10 15
    L2: 20
    L3: 30 35 40 45 50

    k = 4length(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将在第一次select函数调用中接收到 45 个元素的整个数组，并且将数组L周围分开的相同分区逻辑M = 30将应用于最终获得中位数的中位数。

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

于 2015-01-22T12:51:20.760 回答