algorithm - 中位数算法的中位数：为什么将数组分成大小为 5 的块

Question

在中位数算法中，我们需要将数组分成大小为 5 的块。我想知道算法的发明者是如何想出幻数“5”而不是，可能是 7，或 9 或别的东西？

Answer 1

该算法的数字必须大于 3（显然是奇数）。5 是大于 3 的最小奇数。所以选择了 5。

Answer 2

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

中位数计算递归调用不会超过最坏情况的线性行为，因为中位数列表是列表大小的 20%，而另一个递归调用最多在列表的 70% 上递归，使得运行时间

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

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

Answer 3

您还可以使用大小为 3 或 4 的块，如K. Chen 和 A. Dumitrescu (2015)的论文Select with groups of 3 or 4中所示。这个想法是使用“中位数的中位数”算法两次，然后才进行分区。这降低了枢轴的质量，但速度更快。

所以而不是：

T(n) <= T(n/3) + T(2n/3) + O(n)
T(n) = O(nlogn)

一个得到：

T(n) <= T(n/9) + T(7n/9) + O(n)
T(n) = Theta(n)

Answer 4

请参阅Brilliant.org上的说明。基本上，五是我们可以用来维持线性时间的最小可能数组。使用 n=5 大小的数组也很容易实现线性排序。为乳胶道歉：

为什么是 5？

中位数的中位数将列表划分为长度为 5 的子列表以获得最佳运行时间。请记住，通过蛮力（排序）找到小列表的中位数需要很短的时间，因此子列表的长度必须相当小。但是，例如，将子列表大小调整为 3 确实会使运行时间变得更糟。

如果算法将列表划分为长度为 3 的子列表，则 pp 将大于大约 \frac{n}{3} 3 n ​ 个元素，并且它将小于大约 \frac{n}{3} 3 n 个​元素。这将导致最坏的情况 \frac{2n}{3} 3 2n ​ 递归，产生递归 T(n) = T\big( \frac{n}{3}\big) + T\big(\frac{ 2n}{3}\big) + O(n),T(n)=T( 3 n ​ )+T( 3 2n ​)+O(n)，根据主定理是 O(n \log n ),O(nlogn)，比线性时间慢。

事实上，对于任何形式的递归 T(n) \leq T(an) + T(bn) + cnT(n)≤T(an)+T(bn)+cn，如果 a + b < 1a+b <1，递归将求解为 O(n)O(n)，如果 a+b > 1a+b>1，则递归通常等于 \Omega(n \log n)Ω(nlogn)。[3]

中位数算法可以使用大于 5 的子列表大小（例如 7）并保持线性运行时间。但是，我们需要使子列表的大小尽可能小，以便可以在有效的恒定时间内对子列表进行排序。