6

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

4

4 回答 4

6

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

于 2013-08-07T06:36:51.700 回答
1

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

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

图片

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

图片

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

于 2013-08-07T06:14:10.717 回答
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)
于 2016-09-02T09:19:54.797 回答
0

请参阅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)并保持线性运行时间。但是,我们需要使子列表的大小尽可能小,以便可以在有效的恒定时间内对子列表进行排序。

于 2020-11-26T04:27:38.813 回答