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