哪里恒5来自于中位数的中位数的算法? [英] Where does the constant 5 come from in the median-of-medians algorithm?
问题描述
我一直在试图理解这里的5来自于的中位数算法中位数一>,但似乎无法找到它是如何得出的简单描述,以及为什么它是最佳的。
I've been trying to understand where the "5" comes from in the Median of Medians algorithm, but can't seem to find a simple description of how it is derived and why it is optimal.
例如,为什么不说7一个可行的选择?
For example, why isn't say 7 a viable option?
我可以看到5唯一的好处是,它具有在作出排序在5个项目不超过3交换一个简单的例子,中间的每一侧2项。
The only advantage I can see for 5 is that it has 2 items on each side of the middle making a sort over the 5 items a simple case of no more than 3 swaps.
推荐答案
5选择,因为它是为它的复发解决为O(n)的最小值。 7工程,以及,但往往要慢一些。
The 5 is chosen because it's the smallest value for which the recurrence solves to O(n). 7 works as well, but tends to be slower.
更具体地:如果你打破了投入的大小5块,你得到这个复发:
More concretely: if you break the input into blocks of size 5, you get this recurrence:
T(N)≤T(N / 5)+ T(7N / 10)+ O(N)
T(n) ≤ T(n/5) + T(7n/10) + O(n)
这解决了以O(N),因为工作每级几何衰变。
This solves to O(n), since the work decays geometrically per level.
如果我们用大小为3块,我们得到
If we use blocks of size 3, we get
T(N)≥T(N / 3)+ T(2π/ 3)+ O(N)
T(n) ≥ T(n/3) + T(2n/3) + O(n)
解决了以与欧米茄(N日志N)
Which solves to Ω(n log n).
选择大小7块给
T(N)≤T(N / 7)+ T(5N / 7)+ O(N)
T(n) ≤ T(n / 7) + T(5n / 7) + O(n)
这也解决了为O(n)的,因为工作的几何衰变。然而,恒定在大O术语是比在5情况,因为分拣和服用尺寸7的n个/ 7块的位数是比排序并考虑大小5.正/ 5块的位数因此更多的工作较大, - 即用五个街区的情况下使用较为普遍。
This also solves to O(n) because the work decays geometrically. However, the constant in the big-O term is larger than in the 5 case because sorting and taking the median of n/7 blocks of size 7 is more work than sorting and taking the median of n/5 blocks of size 5. Accordingly, the blocks-of-five case is used more commonly.
希望这有助于!
这篇关于哪里恒5来自于中位数的中位数的算法?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!