algorithm - 中位数算法中常数 5 从何而来？

Question

我一直在努力理解 the Median of Medians algorithm 中“5”的来源，但似乎找不到关于它是如何推导出来的以及为什么它是最佳的简单描述。

例如，为什么说 7 不是一个可行的选择？

我能看到 5 的唯一优势是它在中间的每一侧都有 2 个项目，这使得对 5 个项目进行排序成为不超过 3 个交换的简单情况。

Answer 1

选择 5 是因为它是递归求解为 O(n) 的最小值。 7 也可以工作，但速度往往较慢。

更具体地说:如果将输入分成大小为 5 的 block ，则会重复出现:

T(n) ≤ T(n/5) + T(7n/10) + O(n)

这解决了 O(n)，因为工作在每个级别上呈几何衰减。

如果我们使用大小为 3 的 block ，我们得到

T(n) ≥ T(n/3) + T(2n/3) + O(n)

求解为 Ω(n log n)。

选择大小为 7 的 block 给出

T(n) ≤ T(n / 7) + T(5n / 7) + O(n)

这也解决了 O(n)，因为工作呈几何衰减。但是，大 O 项中的常数大于 5 情况下的常数，因为排序和取 n/7 个大小为 7 的 block 的中值比排序和取 n/5 个大小为 5 的 block 的中值更费力。因此, 五 block 的情况更常用。

希望这对您有所帮助!