中位数选择的最佳中位数 - 3个元素块与5个元素块？

Question

我正在研究一种基于Select算法的快速变量实现,用于选择一个好的枢轴元素.传统智慧似乎是将数组划分为5个元素块,取每个元素的中位数,然后递归地将相同的阻塞方法应用于得到的中位数以获得"中位数中位数".

令我困惑的是选择5元素块而不是3元素块.对于5元素块,在我看来,你执行n/4 = n/5 + n/25 + n/125 + n/625 + ...5个中值运算,而对于3个元素块,你执行n/2 = n/3 + n/9 + n/27 + n/81 + ...3个中值运算.由于每个5的中位数是6个比较,并且每个中位数3是2个比较,这导致3*n/2使用5的n中位数和使用3的中位数进行比较.

任何人都可以解释这种差异,使用5元素块的动机是什么？我不熟悉应用这些算法的常规做法,所以也许你可以通过某种方式减少一些步骤,并且仍然能够"足够接近"中位数以确保良好的转向,并且这种方法可以更好地使用5元素块？

Answer 1

原因是通过选择3的块,我们可能会失去使用O(n)时间算法的保证.

对于5的块,时间复杂度是

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

对于3块,它出来了

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

看看这个:http://www.cs.berkeley.edu/~luca/w4231/fall99/slides/l3.pdf

Answer 2

我认为这与确保"好"分裂有关.划分为5个元素块可确保70-30的最坏情况分割.标准论证如下:在n/5块中,至少有一半的中位数> =中位数的中位数,因此至少有一半的n/5块具有至少3个元素(1/2的1/2)> =中位数 -中位数,这给出了一个3n/10分裂,这意味着另一个分区是7n/10最坏的情况.

这给了T(n) = T(n/5) + T(7n/10) + O(n).

因为n/5 + 7n/10 < 1,最坏情况下的运行时间是O(n).

因此,选择3元素块使得:至少一半的n/3块具有至少2个元素> =中值中值,因此这给出了n/3分裂,或者2n/3在最坏的情况下.

这给了T(n) = T(n/3) + T(2n/3) + O(n).

在这种情况下,n/3 + 2n/3 = 1因此在最坏的情况下它减少到O(n log n).