中位数算法中位数:为什么将数组划分为大小为5的块

Question

在中位数的中位数算法,我们需要将阵列分成大小五大块我不知道怎么的算法发明者与神奇数字想出了"5",而不是,可能是7或9或别的什么？

Answer 1

该算法的数量必须大于3(显然是奇数).5是大于3的最小奇数.因此选择5.

Answer 2

我认为，如果您检查 wiki 页面的“O(n) 运行时间证明”部分，了解中位数算法：

计算中值的递归调用不会超过最坏情况的线性行为，因为中值列表是列表大小的 20%，而另一个递归调用最多递归列表的 70%，从而缩短了运行时间

O(n) 项 cn 用于分区工作（我们对每个元素进行固定次数的访问，以便将它们分成 n/5 组并在 O(1) 时间内获取每个中值）。由此，利用归纳法，我们可以很容易地证明

这应该可以帮助您理解为什么。