QuickSort的时间表现

Question

QuickSort算法对10.000.000个数字进行排序。运行时间为5.3秒。我想知道如果有1,000,000,000个数字，什么是运行时间。

大概需要681秒是合乎逻辑的吗？

（这是一个假设性的问题，所以我们不依赖于计算机的RAM或CPU性能比较。）

Answer 1

快速排序的运行时间，平均为O（n log n）的。假设运行时对于某个常量c具有c n log n的形式。你知道，当n = 10,000,000运行时间为5.3s，所以我们得到

10,000,000Ç登录10,000,000 = 5.3s

10,000,000 C＆middot; 7 = 5.3s

C = 75.71ns

现在让我们插上的N = 1,000,000,000：

C N日志N =

75.71ns＆middot; 1,000,000,000＆middot;登录十亿

= 681.43s

所以，是的，你的估计是合理的。

Answer 2

上的快速排序维基百科页面： https://en.wikipedia.org/wiki/Quicksort

StackOverflow的最坏情况： Worst case for QuickSort - when can it occur?

这是回答对数学论坛的复杂性： https://math.stackexchange.com/questions/96767/worst-case-complexity-of-the-quicksort-algorithm

这里是关于时间的答案： https://math.stackexchange.com/questions/1071229/expected-time-of-quicksort?rq=1