7

我已经阅读了订单统计信息，以在线性时间 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 表示数字足够大。

4

1 回答 1

3

让我们将...的中位数的中位数表示为 [median of]* = 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。

您提出的 [median of]* 算法的运行时间将是：

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。

于 2013-07-10T23:43:44.703 回答