我已经阅读了顺序统计信息,以便在线性时间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 …