中位数的中位数

Question

我已经阅读了顺序统计信息，以在线性时间 O(n) 内找到大小为 n 的数组中的第 k 个最小(或最大)元素。

有一个步骤需要找到中位数的中位数。

1. 将数组拆分为 [n/5] 个部分。每个部分有 5 个元素。
2. 求每个部分的中位数。 (我们现在有 [n/5] 个号码)
3. 重复步骤 1 和 2，直到我们只剩下最后一个数字。 (即递归)

T(n) = T(n/5) + O(n)我们可以得到 T(n) = O(n)。

但是，如果我们有一个很大的数组，我们最终得到的数字是不是不是中位数的中位数，而是中位数的中位数的中位数的中位数的中位数的中位数。

请考虑一个包含 125 个元素的数组。

首先，将其分为 25 个部分，我们找到 25 个中位数。然后，我们将这 25 个数字分成 5 个部分，并找到 5 个中位数，最后，我们得到中位数的中位数。 (不是中位数的中位数)

我关心它的原因是，我可以理解最多有大约 [3/4]*n 个元素小于(或大于)中位数的中位数。但如果不是中位数的中位数，而是中位数的中位数的中位数呢？在最坏的情况下，小于(或大于)主元的元素一定较少，这意味着主元更接近数组的边界。

如果我们有一个非常大的数组，并且我们找到了它的中位数的中位数的中位数的中位数的中位数的中位数的中位数的中位数。在最坏的情况下，我们发现的主元仍然可以非常接近边界，这种情况下的时间复杂度是多少？

我构建了一个包含 125 个元素的数据集。结果是9吗？

0.8 0.9 1 inf inf
1.8 1.9 2 inf inf
6.8 6.9 7 inf inf
inf inf inf inf inf
inf inf inf inf inf

2.8 2.9 3 inf inf
3.8 3.9 4 inf inf
7.8 7.9 8 inf inf
inf inf inf inf inf
inf inf inf inf inf

4.8 4.9 5 inf inf
5.8 5.9 6 inf inf
8.8 8.9 9 inf inf
inf inf inf inf inf
inf inf inf inf inf

inf inf inf inf inf
inf inf inf inf inf
inf inf inf inf inf
inf inf inf inf inf
inf inf inf inf inf

inf inf inf inf inf
inf inf inf inf inf
inf inf inf inf inf
inf inf inf inf inf
inf inf inf inf inf

其中 inf 表示数字足够大。

Answer 1

让我们将...的中位数的中位数表示为[中位数]* = M。

首先，我相信中位数算法(选择一个好的主元)不是递归的。算法如下:

1. 将元素分成 5 组
2. 求每组的中位数
3. 找到中位数的中位数并将其用作枢轴。

中位数的中位数将小于 3n/10 个元素并大于另一个 3n/10 个元素，而不是 3n/4。选择中位数后，您有 n/5 个数字。中位数的中位数大于/小于这些数字的一半，即 n/10。这些数字中的每一个本身都是中位数，因此它大于/小于 2 个数字，从而得到另外 2n/10 个数字。现在，您总共得到 n/10 + 2n/10 = 3n/10 个数字。

为了解决您的第二个问题，在收集示例数据集中的 5 组并计算其中位数后，我们将得到以下序列:

1, 2, 7, inf, inf
3, 4, 8, inf, inf
5, 6, 9, inf, inf, 
inf, inf, inf, inf, inf, 
inf, inf, inf, inf, inf.

所以中位数的中位数确实是 9。

您建议的[中位数]*算法的运行时间将为:

T(n) = O(n * log(n))

现在让我们尝试分析有多少个数字小于/大于M。我们有以下小组:

• 深度 1:n/5 个元素均为中位数
• 深度 2:n/25 个元素均为中位数
• ...
• 深度 i:n/(5^i) 个元素，所有中位数

每组小于/大于前一个深度的2个元素，即小于/大于前一个深度的2个元素，依此类推:

总计计算，我们得到M大于/小于 (n * (2^k) + k * n)/((2^k) * (5^k) )。对于深度 = 1，您将得到中位数的中位数，即 3n/10。

现在假设您的深度为 [log_5 (n)]，即 n = 5^k，我们得到:

5^k * (k + 2^k)/(5^k * 2^k) 即 -> 1。