algorithm - 中位数的中位数大示例

Question

您好，我想了解中位数算法的中位数是如何工作的。到目前为止，在我看到的所有示例中，在算法开始执行之前，就已经存在被划分的数字组。所以我无法理解这些组是如何组成的。更具体地说，在目前研究的示例中，声明有 9 组，每组 5 个数字，例如 45 个数字，或 4 组 10 个数字，也就是 40 个数字。那么如果我们有n个数字怎么办？我应该遵循什么好的技术来找到它的组应该有的元素数量？

Answer 1

MoM 是一种递归算法。它作为一种为快速排序或快速选择等算法选择“枢轴”的合理方式而存在。因此，它需要在一定的时间范围内运行。

如果将其解释为基本案例和递归案例，可能会更容易理解。

基本情况很清楚。如果列表中的元素少于五个，那么您会以幼稚的方式找到中位数。

但是，如果您的列表至少有五个元素，则可以应用递归情况。你将从你的大列表中取出连续的五个元素组，找到它们的中值，并将其添加到一个较小的列表中。（如果你有一些剩余，你可以忽略它们。）

如果这个新的、较小的列表足够小，您可以应用基本情况，如上所述。否则，您将通过“小”列表创建另一个更小的列表。起泡、冲洗并重复，直到剩下的元素少于五个。这就是你对整体中位数的估计。所以它适用于任何大小的列表。

那么“五”应该有多大？好吧，事实证明 5 是最优的。有人在该主题的 Wikipedia 页面上展示了复杂性分析。从本质上讲，“五”的较大值可以让您更好地逼近中位数，但需要花费更多的工作来找到“五”的中位数。不幸的是，3 并没有将每次迭代的搜索空间减少到足以成为“5”的值得选择的程度。它通常需要很奇怪，除非您想花费周期来划分元素之间的差异。