哪里恒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屋！