随机中位数快排比随机快排表现更好吗？

Question

我刚刚回答了一个关于在快速排序实现中选择分区的不同方法的问题，然后遇到了一个问题，我真的不知道如何回答。这有点数学重，这可能不是提问的正确网站，所以如果需要移动，请告诉我，我会很乐意将其迁移到其他地方。

众所周知，随机选择枢轴的快速排序实现最终将在预期的O(n lg n)时间内运行（在维基百科上有一个很好的证明）。然而，由于生成随机数的成本，许多快速排序实现不会随机选择枢轴，而是依赖于“三数中值”方法，在该方法中确定性地选择三个元素，并从中选择中位数作为枢轴。众所周知，这会退化为最坏情况下的O(n^2)（例如，这篇论文介绍了如何生成这些最坏情况的输入）。

现在，假设我们通过从序列中选择三个随机元素并使用它们的中位数作为枢轴的选择来结合这两种方法。我知道这也可以使用略有不同的证明保证O(n lg n)平均运行时间。然而，我不知道在此特定快速排序实现中n lg n项前面的常数因子是多少。对于常规随机化快速排序，维基百科列出了随机化快速排序的实际运行时间至多需要1.39 n lg n比较（使用二进制对数作为lg）。

我的问题是：是否有人知道如何推导使用“三数中值”随机快速排序的比较次数的常数因子？更普遍地说，是否有一个表达式来计算使用随机中位数为基准的快速排序的常数因子？我很好奇，因为我认为如果这种方法存在某种“黄金点”，可以使比其他随机快速排序实现少进行比较。我的意思是，能不能说使用随机中位数选择的随机快速排序会进行最少的比较？或者可以明确地说你只需随机选择一个枢轴元素？

- templatetypedef

---

生成三个随机数会比生成一个随机数更加昂贵吗？ - Lasse V. Karlsen

是的，但是非常高的概率（例如，1-1/n^2），我们只需要总共O(n)个随机数。渐近地，这并不代表一个显著的额外成本。 - a dabbler

对于一个好问题，我会给予+1的评分。如果可能的话，如果提供生成最坏情况输入的链接，我会额外给予+0.5的评分。 - DarenW

@LasseV.Karlsen 你有什么建议？标准库中的qsort实现已经比选择中值作为枢轴的性能更好了。 - Aditya P

@templatetypedef 那么你的结论是什么？使用随机中位数为六个元素的随机快速排序可以使比较次数最少吗？还是随机选择一个枢轴元素？ - Aditya P

Answer 1

这里是常数的启发式推导。我认为可以花更多的精力使其更加严谨。

设P是一个取值范围在[0,1]之间的连续随机变量。直观地说，P是小于枢轴的值的比例。我们要找到常数c，使得

c n 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的概率密度函数为1。常数为

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

Out[1]= 1.38629

当中值为3的时候，P的概率密度函数为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

- userOVER9000

---

对于2k + 1个元素的中位数，概率密度函数为(2k + 1)!/(k!)^2 * x^k (1 - x)^k。加油！ - userOVER9000

@userOVER9000- 这看起来很不错，但是你的逻辑没有考虑到为了计算k的中位数所做的额外比较，也没有处理我们在离散域而不是连续域中工作的事实。有没有办法解决这个问题？ - templatetypedef

额外的比较：正如“业余爱好者”所指出的那样，这些最多是由主定理线性的。离散而非连续：我们可以将P与中位数索引的实际分布相耦合，并用O(1/n)的误差从递归中省略枢轴。经过一堆乏味的分析后，总误差应该是线性的。 - userOVER9000

Answer 2

通常随机快速排序算法的常数很容易计算，因为相隔k个位置的两个元素被比较的概率恰好为2/(k+1)：在这两个元素中的任意一个在它们之间的k-1个元素之前被选为枢轴的概率。不幸的是，对于你的算法没有类似的巧妙方法。

我不敢尝试回答你加粗的问题，因为我能够回答你“根本”的问题：从渐进意义上讲，不存在“甜点”。计算k个元素的中位数的总成本，即使是O(n^{1 - ε})个元素，也是线性的，而nlogn项的常数随着数组被均匀分割而减少。当然，问题在于线性项上的常数非常不切实际，这突显了渐进分析的缺点之一。

基于下面我的评论，我猜测k = O(n^α)，其中0 < α < 1是“甜点”。

- a dabbler

---

为什么说“甚至是O(n^{1 - ε})个元素”，而不是更强且同样正确的“甚至是所有n个元素”？ - Peter Taylor

我正在对所有递归调用求和。所有的n都会导致(n log n)大小的成本。 - a dabbler

即使 n^ε，也足以得到最佳的n log n常数。 - a dabbler

即使使用 polylog 也可能奏效，但我无法在脑海中处理细节。 - a dabbler

Answer 3

如果集合的初始状态是随机排序的，那么随机挑选3个项目来计算中位数所得到的精确度与使用确定性方法挑选3个项目相同。采用随机选择项目的动机在于，确定性方法得出的结果可能比平均水平更差。如果确定性方法能够得出良好的中位数，则不能通过随机挑选项目来改进它。

因此，哪种方法能够得出最佳结果取决于输入数据，不能为每个可能的集合确定最优解。唯一确定降低常数因子的方法是增加计算中位数所需的项目数量，但是在某些情况下，计算中位数的成本将比获得更好的中位数价值更高。

- Guffa

---

为什么要点踩？如果你不解释哪里有问题，那么答案就无法得到改进。 - Guffa

Answer 4

是的，它确实可以。C标准库中的qsort函数的作者Bentley和McIlroy在他们的论文Engineering a Sort Function中给出了以下数字：

• 使用第一个、中间或随机枢轴的平均比较次数为1.386 n lg n
• 使用中位数枢轴的平均比较次数为1.188 n lg n
• 使用三个中位数枢轴的平均比较次数为1.094 n lg n

根据上述论文：

因此，我们的最终代码选择较小数组的中间元素，中等大小数组的第一个、中间和最后一个元素的中位数，以及大数组的九个均匀间隔元素的伪中位数。

- Robert S. Barnes

---

这似乎是一种伪随机的方法，尝试实现第一篇帖子中所述的三个随机元素中位数枢轴。使用随机数作为枢轴真的很耗费资源吗？ - Aditya P

Answer 5

只是一个想法：如果你使用了“三数中值法”，并且发现它更好，为什么不使用“五数中值法”或者“十一数中值法”呢？顺便说一下，当你处理的时候，也许可以考虑一个“n个数中值法”的优化……嗯……好吧，显然这是个糟糕的主意（因为你需要对序列进行排序）。

基本上，要选择将你的轴元素选择为“m个数中值”的元素，你需要对这“m”个元素进行排序，对吧？ 因此，我猜其中一个你正在寻找的常数就是 “2”：通过首先对3个元素进行排序来选择你的轴元素，你会执行多少额外的比较？假设是2。你一次又一次地在快速排序中做这个操作。一个基本的结论是，“三数中值法”因此比简单的随机快速排序慢2倍。

但是，在这里有什么起作用呢？你得到了一个更好的分治分布，并且在某种程度上更好地防止了退化情况的发生。

那么，回到我一开始提出的臭名昭著的问题：为什么不从中位数（m为5、7、n/3等）中选择枢轴元素呢？必须有一个甜点，在这个点上，排序m个元素的代价比更好的分治行为和快速排序的收益更大。我猜，这个甜点很早就存在了——如果你选择中位数-3，首先要对抗的是常数因子2次比较。我承认这值得一试，但我不会对结果过于期待 :-) 但如果我错了，而且收益巨大：不要止步于3！

- towi

---

这个页面底部建议使用median-of-sqrt(N/log(N))。他是怎么得出这个结论的，我真的不理解。http://www.inference.phy.cam.ac.uk/mackay/sorting/sorting.html - Rob Neuhaus

有意思。这个家伙做了他的数学，而我只是在猜测。实际上，“70”让我想起了什么，我想我以前听过这个“甜蜜点”的数字。 - towi