为什么quicksort的常数因子比heapsort更好？

Question

根据我的计算:

• 快速成本= n +(n/2 + n/2)+(n/4 + n/4 + n/4 + n/4)+ ... = n*log(n)= log(n ⁿ)
• 对于i = n,n-1,n-2,...,1 = log(n!),堆的成本= sum [log(i)]

为什么说quicksort比heapsort有更好的常数因子,因此快速排序比heapsort平均更好？是不是log(n ⁿ)> log(n!)？

Answer 1

我认为这里的问题是你对quicksort和heapsort的分析不够精确,无法说明为什么常数因素会有所不同.

你的确可以证明,平均而言,quicksort将比heapsort做更多的比较(快速排序大约为1.44 n log ₂ n,而对于heapsort大约为n log ₂ n).但是,比较并不是heapsort和quicksort运行时的唯一决定因素.

快速排序更快的主要原因是参考地点. 由于内存缓存的工作方式,在彼此相邻的位置中的数组访问往往比分散在整个数组中的数组访问快得多.在快速排序中,分区步骤通常在数组的末尾执行所有读取和写入操作,因此数组访问彼此密切相关.另一方面,Heapsort在数组上下移动时跳转到数组.因此,平均而言,快速排序中的数组访问所花费的时间比堆栈中的数组访问少得多.差异足够大,以至于快速排序中n log n项前面的常数因子低于heapsort中n log n项前面的常数因子,这是快速排序比密码短得多的一个原因.

简而言之 - 如果我们所关心的只是比较,那么heapsort比quicksort更好.但由于内存系统使用缓存并且缓存未命中是昂贵的,因此快速排序通常是更好的选择.

另外,请注意,通过斯特林的近似,log(n ⁿ)= n log n和log(n!)= n log n - n + O(log n).这意味着log(n!)并不比n log n小很多,即使n非常大.肯定存在差异,但它并不足以让自己产生巨大影响.

希望这可以帮助!

Answer 2

以下是Steven S. Skiena的算法设计手册中的段落,该手册讨论了三个O(nlogn)排序算法之间的速度:

但是我们如何比较两个Θ(n log n)算法来决定哪个更快？我们如何证明快速排序真的很快？不幸的是, RAM模型和Big Oh分析提供了太多粗略的工具来进行这种区分.当面对具有相同渐近复杂度的算法时,实现细节和系统怪癖(例如高速缓存性能和内存大小)可能被证明是决定性因素.

我们可以说的是,实验表明,如果实施正确实施的快速排序,它通常比mergesort或heapsort快2-3倍.主要原因是最内层循环中的操作更简单.但是,当我说快速排序更快时,如果你不相信我,我不能和你争辩. 这是一个问题,其解决方案不在我们使用的分析工具之外.最好的方法是实现算法和实验.

-4.6.3"Quicksort真的很快吗？",算法设计手册