中间值

Question

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

有一步，它需要找到中间值的中位数。

1. 将数组分成n/5部分。每个部分有5个元素。
2. 找到每个部分的中间值。(我们现在有n/5的号码)
3. 重复第一步和第二步，直到我们只有最后一个数字。(即递归)

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。