了解“中位数中位数”算法

  • Z时代
  • 2024-01-10
  • 分类：问答

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

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

因此，我认为在某些情况下，这种递归可能不会返回真实的中位数。我想知道我的错误在哪里。

回答：

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

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 1510。在内部，这会将组分为五个块，并对其进行排序，依此类推，但是这样做是为了确定分区步骤的划分点，并且在此分区步骤中，递归调用将找到中位数的真实中位数，在这种情况下将为30。如果您使用30作为中值作为原始算法中的划分步骤，则确实确实会根据需要获得很好的分割。

希望这可以帮助！

以上是 了解“中位数中位数”算法 的全部内容， 来源链接： utcz.com/qa/400899.html

回到顶部