Medians中位数
我已经阅读了订单统计数据，以线性时间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表示数量足够大。
让我们用...表示您的中位数的中位数，作为[中位数] * = 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。
链接地址: http://www.djcxy.com/p/14659.html上一篇: Median of Medians
下一篇: Unable to bind values after inserting table rows with jquery