中位数中的中位数算法让我感到困惑

Question

中位数中的中位数算法让我感到困惑

4

有一件关于中位数算法的事情我不太明白。该算法的一个关键步骤是找到一个近似中位数，并且根据维基百科，我们保证这个近似中位数大于初始集合的30％元素。

为了找到这个近似中位数，我们计算每组5个元素的中位数，将这些中位数收集到一个新集合中，并重新计算中位数，直到得到的集合少于5个元素。在这种情况下，我们得到集合的中位数。（如果我的解释不清楚，请参见维基百科页面）

但是，请考虑以下125个元素的集合：

1 2 3 1001 1002
4 5 6 1003 1004
7 8 9 1005 1006
1020 1021 1022 1023 1034 
1025 1026 1027 1028 1035 

10 11 12 1007 1008
13 14 15 1009 1010
16 17 18 1011 1013
1029 1030 1031 1032 1033 
1036 1037 1038 1039 1040 

19 20 21 1014 1015
22 23 24 1016 1017
25 26 27 1018 1019
1041 1042 1043 1044 1045
1046 1047 1048 1049 1050

1051 1052 1053 1054 1055
1056 1057 1058 1059 1060
1061 1062 1063 1064 1065
1066 1067 1068 1069 1070
1071 1072 1073 1074 1075

1076 1077 1078 1079 1080
1081 1082 1083 1084 1085
1086 1087 1088 1089 1090
1091 1092 1093 1094 1095
1096 1097 1098 1099 1100

所以我们把这个集合分成5个元素一组，计算并收集中位数，因此我们得到以下集合：

3 6 9 1022 1207
12 15 18 1031 1038
21 24 27 1043 1048
1053 1058 1063 1068 1073
1078 1083 1088 1093 1098

我们重新执行了相同的算法，得到了以下集合：

9 18 27 1063 1068

所以我们得出近似中位数为27。但是这个数字大于或等于仅有的27个元素。而27/125 = 21.6% < 30%!!

所以我的问题是：我错在哪里了？？为什么在我的情况下近似中位数不大于30％的元素？？？

谢谢您的回复！！

- Truc Truca

2个回答

3

我完全同意您的分析，直到您得到每个五个元素块的中位数时，您会剩下这些元素:

3 6 9 1022 1207 12 15 18 1031 1038  21 24 27 1043 1048 1053 1058 1063 1068 1073 1078 1083 1088 1093 1098

您说得对，目前我们需要得到这些元素的中位数。但是中位数算法的实现方式与您提出的方法不同。

在您进行分析时，您尝试通过再次将输入拆分为大小为五的块并取每个块的中位数来获取这组值的中位数。然而，这种方法实际上不会给您中位数。（您可以通过注意到您得到了27来看到这一点，这不是那些价值观的真正中位数）。

中位数算法实际上是通过递归调用整个算法以获取这些元素的中位数来获取中位数的中位数的。这与仅将事物反复分解成块并计算每个块的中位数略有不同。特别是，每个递归调用将执行以下操作：

使用五组启发式方法估计枢轴点
对自身递归调用函数以找到那些中位数的中位数
根据该中位数应用分区步骤，并使用它确定如何从那里继续。

在我看来，该算法过于复杂，无法手动跟踪。您确实需要相信，由于每个递归调用都使用比开始时更小的数组进行工作，因此每个递归调用确实会执行所需的操作。因此，当您像以前那样只剩下每个组的中位数时，应该相信当您需要通过递归调用获得中位数时，您最终会得到真正的中位数。

如果您查看在第一步生成的中位数的中位数，则会发现它实际上将介于原始数据集的第30至70个百分位之间。

如果这看起来很困惑，请不要担心-您非常出色。这种算法是出了名的棘手。对我而言，理解它的最简单方法就是相信递归工作，并仅跟踪一层深度，假设所有递归调用都有效，而不是尝试走到递归树的底部。

- templatetypedef

据我从维基百科页面了解，中位数算法并不在中位数-5列表上递归调用自身，而是调用快速选择算法，然后再调用中位数算法。区别在于快速选择返回实际的中位数，而不是近似中位数。这个理解正确吗？ - m69 ''snarky and unwelcoming''

中位数算法与快速选择算法是相互独立的，所以它不应该对快速选择算法进行任何递归调用。（快速选择是一种随机选择算法，它随机选择枢轴。中位数算法之所以成为重大发现，其中一个原因是它完全确定性，并具有最坏情况下的效率）。 - templatetypedef

嗯，那么维基百科的文章最好是令人困惑的，可能是不正确的。 - m69 ''snarky and unwelcoming''

1

@m69 是的，我同意。我想我应该去修复它。 :-) - templatetypedef

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- m69 ''snarky and unwelcoming'' · Accepted Answer

您对中位数算法的困惑是由于在算法的某些阶段需要计算精确中位数，而中位数算法返回的结果只是实际中位数的近似值，误差不超过20％。如果您混淆这两个概念，将无法获得预期的结果，正如您的示例中演示的那样。

中位数算法使用三个函数作为其构建模块：

medianOfFive(array, first, last) {
    // ...
    return median;
}

此函数从数组的一部分中返回五个（或更少）元素的确切中位数。有几种编码方法，例如基于排序网络或插入排序。细节对于本问题并不重要，但重要的是要注意，此函数返回确切的中位数，而不是近似值。

medianOfMedians(array, first, last) {
    // ...
    return median;
}

这个函数从（部分）数组中返回中位数的近似值，保证比30%最小的元素大，并且比30%最大的元素小。我们将在下面更详细地讨论。

select(array, first, last, n) {
    // ...
    return element;
}

这个函数从一个数组（的一部分）中返回第n小的元素。该函数返回确切的结果，而不是近似值。

在其最基本的形式下，整体算法的工作方式如下：

medianOfMedians(array, first, last) {
    call medianOfFive() for every group of five elements
    fill an array with these medians
    call select() for this array to find the middle element
    return this middle element (i.e. the median of medians)
}

所以你的计算出现了错误。在创建了一个使用五数中位数的数组后，你又在这个数组上再次使用了中位数函数，得到了一个近似中位数（27），但是你需要的是实际中位数（1038）。

这听起来相当简单，但问题在于函数select()调用medianOfMedians()来获得中位数的第一个估计值，然后使用它来计算准确的中位数，因此你会得到一个双向递归，其中两个函数互相调用。这种递归停止的条件是medianOfMedians()被调用的元素数量少于25个，因为那时只有5个中位数，而不是使用select()来找到它们的中位数，它可以使用medianOfFive()。

select()调用medianOfMedians()的原因是它使用分区将（部分）数组分成接近相等大小的两部分，并且它需要一个好的枢轴值来执行此操作。在将数组分成具有较小和较大元素的两部分之后，它检查n-th最小元素在哪一部分中，并递归地处理该部分。如果具有较小值的部分的大小为n-1，则枢轴值是第n个值，不需要进一步递归。

select(array, first, last, n) {
    call medianOfMedians() to get approximate median as pivot
    partition (the range of) the array into smaller and larger than pivot
    if part with smaller elements is size n-1, return pivot
    call select() on the part which contains the n-th element
}

如您所见，select()函数会进行递归（除非枢轴刚好是第n个元素），但是它只在数组的较小范围内进行，因此在某个时刻（例如两个元素）查找第n个元素将变得非常简单，不再需要进一步递归。

所以最终我们会得到更详细的内容：

medianOfFive(array, first, last) {
    // some algorithmic magic ...
    return median;
}

medianOfMedians(array, first, last) {
    if 5 elements or fewer, call medianOfFive() and return result
    call medianOfFive() for every group of five elements
    store the results in an array medians[]
    if 5 elements or fewer, call medianOfFive() and return result
    call select(medians[]) to find the middle element
    return the result (i.e. the median of medians)
}

select(array, first, last, n) {
    if 2 elements, compare and return n-th element
    if 5 elements or fewer, call medianOfFive() to get median as pivot
    else call medianOfMedians() to get approximate median as pivot
    partition (the range of) the array into smaller and larger than pivot
    if part with smaller elements is size n-1, return pivot
    if n-th value is in part with larger values, recalculate value of n
    call select() on the part which contains the n-th element
}

例子

输入数组（125个值，25组每组五个）：

 #1    #2    #3    #4    #5    #6    #7    #8    #9    #10   #11   #12   #13   #14   #15   #16   #17   #18   #19   #20   #21   #22   #23   #24   #25

   1     4     7  1020  1025    10    13    16  1029  1036    19    22    25  1041  1046  1051  1056  1061  1066  1071  1076  1081  1086  1091  1096
   2     5     8  1021  1026    11    14    17  1030  1037    20    23    26  1042  1047  1052  1057  1062  1067  1072  1077  1082  1087  1092  1097
   3     6     9  1022  1027    12    15    18  1031  1038    21    24    27  1043  1048  1053  1058  1063  1068  1073  1078  1083  1088  1093  1098
1001  1003  1005  1023  1028  1007  1009  1011  1032  1039  1014  1016  1018  1044  1049  1054  1059  1064  1069  1074  1079  1084  1089  1094  1099
1002  1004  1006  1034  1035  1008  1010  1013  1033  1040  1015  1017  1019  1045  1050  1055  1060  1065  1070  1075  1080  1085  1090  1095  1100

五个数据一组的中位数（25个值）：

3, 6, 9, 1022, 1027, 12, 15, 18, 1031, 1038, 21, 24, 27, 1043,  
1048, 1053, 1058, 1063, 1068, 1073, 1078, 1083, 1088, 1093, 1098

每组五个数求近似中位数：

 #1    #2    #3    #4    #5

   3    12    21  1053  1078
   6    15    24  1058  1083
   9    18    27  1063  1088
1022  1031  1043  1068  1096
1027  1038  1048  1073  1098

使用五个数值的中位数来近似计算中位数：

9, 18, 27, 1063, 1088

采用近似中位数作为枢轴：

使用pivot 27进行五分区的中位数（取决于方法）：

small: 3, 6, 9, 24, 21, 12, 15, 18
pivot: 27
large: 1031, 1038, 1027, 1022, 1043, 1048, 1053, 1058,  
       1063, 1068, 1073, 1078, 1083, 1088, 1093, 1098

这里有两组，一小一大，分别包含8个和16个元素。我们要在25个元素中找到第13个，所以现在需要在16个元素中找到第4个：

每组五个元素：

 #1    #2    #3    #4

1031  1048  1073  1098
1038  1053  1078
1027  1058  1083
1022  1063  1088
1043  1068  1093

五个一组的中位数：

1031, 1058, 1083, 1098

以近似中位数作为枢轴：

在使用枢轴值为1058的五个分区方法中，中位数的范围如下：

small: 1031, 1038, 1027, 1022, 1043, 1048, 1053
pivot: 1058
large: 1063, 1068, 1073, 1078, 1083, 1088, 1093, 1098

这个较小的组有7个元素。我们正在寻找16个元素中的第4个元素，现在我们要在7个元素中寻找第4个元素：

每组5个元素：

每组五个数的中位数：

1031, 1048

以近似中位数作为枢轴：

使用枢轴值1031进行五路划分的中位数范围（取决于方法）：

small: 1022, 1027
pivot: 1031
large: 1038, 1043, 1048, 1053

小部分有2个元素，大部分有4个元素，所以现在我们要查找4-2-1=1个元素（从4个元素中找出第一个）：

以五个数的中位数为枢轴：

使用枢轴值1043分成五个部分后的中位数范围（取决于方法）：

small: 1038
pivot: 1043
large: 1048, 1053

较小的部分只有一个元素，我们正在寻找第一个元素，因此我们可以返回较小的元素1038。正如您所看到的，1038是原始25个五数中位数的确切中位数，并且在125个原始数组中有62个较小的值。

1 ~ 27, 1001 ~ 1011, 1013 ~ 1023, 1025 ~ 1037

这不仅将其放在30％~70％的范围内，而且意味着它实际上是确切的中位数（请注意，这是这个特定示例的巧合）。