我知道线性选择（中位数算法的中位数）递归方程如下：
T(n) <= an + T(n/5) + T(7n/10)
但是这些术语是从哪里来的呢？我一直在努力理解，但我非常困惑。任何人都可以阐明一下吗？
问问题
2128 次
1 回答
3
Best attempt:
That equation is only for when you do the median of groups of 5. Otherwise it will change. The an part of the equation is the time it takes for the algorithm to go through all the elements and group them into 5. The T(n/5) is the time it takes for the median to be found for each group of 5. As there is n/5 groups of 5.
T(7n/10) will take more time...
When you do the medians of medians the elements are broken up into 4 quadrants. 3/10 of the elements are greater than the median of medians, 3/10 elements are less than the median of medians. The other 4/10 is split up unto 2 groups of 2/10. These are the elements in which you're not sure if they are greater or less than the median of medians. Therefore, the max number of elements you could have that are greater than or less than the median of medians is 3/10 + 2/10 + 2/10 = 7/10. So the T(7n/10) is the part of continuing the equation with the max segment of numbers that is larger/smaller than the median of medians....
Hopefully that kind of makes sense.
于 2015-02-06T18:56:25.430 回答