我一直试图了解“5”在Median of Medians 算法中的来源，但似乎无法找到一个简单的描述来说明它是如何派生的以及为什么它是最优的。
例如，为什么说 7 不是一个可行的选择？
我可以看到 5 的唯一优势是它在中间的每一侧都有 2 个项目，这使得对 5 个项目的排序成为不超过 3 次交换的简单案例。
问问题
442 次
1 回答
5
选择 5 是因为它是递归求解 O(n) 的最小值。7 也可以，但速度较慢。
更具体地说：如果你把输入分成大小为 5 的块，你会得到这个重复：
T(n) ≤ T(n/5) + T(7n/10) + O(n)
这解决了 O(n)，因为工作在每个级别上呈几何衰减。
如果我们使用大小为 3 的块，我们得到
T(n) ≥ T(n/3) + T(2n/3) + O(n)
求解到 Ω(n log n)。
选择大小为 7 的块给出
T(n) ≤ T(n / 7) + T(5n / 7) + O(n)
这也解决了 O(n)，因为工作几何衰减。但是，big-O 项中的常数大于 5 的情况，因为排序和取 n/7 个大小为 7 的块的中位数比排序和取 n/5 个大小为 5 的块的中位数要多。因此，五人一组的情况更常用。
希望这可以帮助！
于 2013-10-31T06:11:26.353 回答