我已经阅读了顺序统计信息,以便在线性时间O(n)中找到大小为n的数组中的第k个最小(或最大)元素.
找到中位数的中位数需要一步.
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表示数字足够大.
让我们将...的中位数的中位数表示为 [median of]* = M。
首先，我相信中位数算法（选择一个好的主元）不是递归的。算法如下：
中位数的中位数将小于 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。我们有以下小组：
每组小于/大于前一个深度的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。