algorithm - 理解 "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)，即集合将分为 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，远小于 wikipedia 中提到的 45 的 30%。

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

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

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

Answer 1

问题出在你说找到中位数的真实中位数的那一步。在您的示例中，您有这些中位数:

50 45 40 35 30 25 20 15 10

这个数据集的真实中位数是 30，而不是 15。您无法通过将组分成五个 block 并取这些中位数的中位数来找到这个中位数，而是通过递归调用这个较小的选择算法团体。您逻辑中的错误是假设通过将上述序列分成两个 block 来找到该组的中位数

50 45 40 35 30

和

25 20 15 10

然后找到每个 block 的中位数。相反，中位数算法将在完整数据集 50 45 40 35 30 25 20 15 10 上递归调用自身。在内部，这会将组分成五个 block 并对它们进行排序等，但这样做是为了确定分区步骤的分区点，并且正是在这个分区步骤中，递归调用将找到中位数的真实中位数，在这种情况下将为 30。如果您使用 30 作为原始算法中的分割步骤的中位数，您确实会根据需要获得非常好的分割。

希望这对您有所帮助!