我一直在试图理解中位数算法中"5"的来源，但似乎找不到关于它是如何推导的以及为什么它是最优的简单描述。
例如，为什么说 7 不是一个可行的选择？
我能看到的 5 个项目的唯一优点是它在中间的每一侧都有 2 个项目，这使得对 5 个项目的排序成为不超过 3 个交换的简单情况。
选择 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 种情况，因为排序和获取大小为 7 的 n/7 块的中位数比排序和获取大小为 5 的 n/5 块的中位数要多。因此，更常用五块的情况。
希望这有帮助！