在中位数算法中,我们需要将数组分成大小为 5 的块。我想知道算法的发明者是如何想出幻数“5”而不是,可能是 7,或 9 或别的东西?
4 回答
该算法的数字必须大于 3(显然是奇数)。5 是大于 3 的最小奇数。所以选择了 5。
我认为,如果您检查 wiki 页面的“O(n) 运行时间证明”部分的中位数算法:
中位数计算递归调用不会超过最坏情况的线性行为,因为中位数列表是列表大小的 20%,而另一个递归调用最多在列表的 70% 上递归,使得运行时间
O(n) 项 cn 用于划分工作(我们以恒定次数访问每个元素,以便将它们形成 n/5 组并在 O(1) 时间内获取每个中值)。由此,使用归纳法,可以很容易地证明
这应该可以帮助您理解为什么。
您还可以使用大小为 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)
请参阅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)并保持线性运行时间。但是,我们需要使子列表的大小尽可能小,以便可以在有效的恒定时间内对子列表进行排序。