我一直试图了解 the Median of Medians algorithm 中“5”的来源，但似乎无法找到关于它是如何导出的以及为什么它是最佳的简单描述。
例如，为什么说 7 不是一个可行的选择？
我能看到 5 的唯一优势是它在中间的每一侧都有 2 个项目，对 5 个项目进行排序，这是一个不超过 3 次交换的简单案例。
最佳答案
选择 5 是因为它是递归求解为 O(n) 的最小值。 7 也能工作，但往往更慢。
更具体地说:如果你把输入分成大小为 5 的块，你会得到这个重复:
这解决了 O(n)，因为工作在每个级别上以几何方式衰减。
如果我们使用大小为 3 的块，我们得到
这解决了Ω(n log n)。
选择大小为 7 的块给出
这也求解为 O(n)，因为工作在几何上衰减。然而，big-O 项中的常数大于 5 情况下的常数，因为排序和取大小为 7 的 n/7 个块的中位数比排序和取大小为 5 的 n/5 个块的中位数工作量更大。因此，五个块的情况更常用。
希望这可以帮助!
关于algorithm - 中位数算法中的常数 5 来自哪里？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19698347/