随机化三分之一的快速排序是否明显优于随机快速排序？

Question

我刚刚回答了一个关于在快速实施中选择分区的不同方法的问题,并提出了一个我真的不知道如何回答的问题.这有点数学,这可能是错误的网站,所以如果这需要移动请告诉我,我很乐意将其迁移到其他地方.

众所周知,随机均匀选择其枢轴的快速实施将最终在预期的O(n lg n)时间内运行(在维基百科上有一个很好的证明).然而,由于产生随机数的成本,许多快速分类实现不会随机选择枢轴,而是依赖于"三分之一"方法,其中确定性地选择三个元素并且选择中值作为枢.众所周知,在最坏的情况下退化为O(n ²)(例如,参见关于如何生成那些最坏情况输入的大文章).

现在,假设我们通过从序列中挑选三个随机元素并使用它们的中位数作为枢轴的选择来组合这两种方法.我知道这也保证了O(n lg n)平均情况运行时使用的证据与常规随机快速排序的证明略有不同.但是,我不知道在这个特定的快速排序实现中,n ng n项前面的常数因子是什么.对于常规随机快速排序维基百科列出随机快速排序的实际运行时间最多需要1.39 n lg n比较(使用lg作为二进制对数).

我的问题是:有没有人知道如何使用"三分之一"随机快速排序得出比较次数的常数因子？如果我们更普遍地说,使用随机的k中值方法是否存在关于快速排序的常数因子的表达式？我很好奇,因为我觉得看看这种方法是否有一些"甜蜜点"比其他随机快速分析实施更少的比较会很有吸引力.我的意思是,能够说随机化的快速排序与随机中位数为六的枢轴选择使得比较最少,这不是很酷吗？或者能够最终说你应该随机选择一个枢轴元素？

Answer 1

这是常量的启发式推导.我认为它可以做得很严谨,付出更多的努力.

令P为连续随机变量,其值为[0,1].直观地,P是小于枢轴的值的分数.我们正在寻找这样的常数c

cn lg n = E [n + c P n lg(P n)+ c(1-P)n lg((1-P)n)].

稍后我们有一点代数

c = 1/E [-P lg P - (1-P)lg(1-P))].

换句话说,c是具有平均值P的伯努利分布的预期熵的倒数.直观地,对于每个元素,我们需要以产生大约lg n位信息的方式将其与枢轴进行比较.

当P是均匀的时,P的pdf是1.常数是

In[1]:= -1/NIntegrate[x Log[2, x] + (1 - x) Log[2, 1 - x], {x, 0, 1}]

Out[1]= 1.38629

当枢轴的中位数为3时,P的pdf为6 x(1 - x).常数是

In[2]:= -1/NIntegrate[6 x (1 - x) (x Log[2, x] + (1 - x) Log[2, 1 - x]), {x, 0, 1}]

Out[2]= 1.18825

Answer 2

通常的随机快速排序的常量很容易计算,因为比较两个元素k个位置的概率正好是2 /(k + 1):这两个元素之一被选为任何一个之前的枢轴的概率他们之间的k-1元素.不幸的是,你的算法没有那么聪明.

我很想尝试你的粗体问题,因为我可以回答你的"潜在"问题:渐渐地说,没有"甜蜜点".计算k个元素的中值,甚至O(n ^{1 - ε})元素的总增加成本是线性的,并且n log n项的常数随着阵列被更均匀地分割而减小.捕获当然是线性项上的常量,这是非常不切实际的,突出了渐近分析的一个缺点.

根据我在下面的评论,我猜0 <α<1的k = O(^nα)是"最佳点".