運行合併排序和快速排序的線性時間

Question

據我所知，我的大學已經證明，對隨機數據進行排序的基於比較的算法的下界是Ω（nlogn）。我也知道Heapsort和Quicksort的平均情況是O（nlgn）。

因此，我試圖繪製這些算法對一組隨機數據進行排序所需的時間。

我使用了發佈在Roseta Code的算法：quicksort和heapsort。當我試圖繪製時間每一個排序隨機數據，多達1萬個號碼需要，我似乎是線性以下圖表：

您還可以找到結果我從運行從here heapsort得到。 此外，您還可以找到我從運行快速排序得到了here

然而調查結果，我得到爲O（n^2）的時間複雜度運行冒泡時，如下面的圖中顯示：

爲什麼這是？我可能會在這裏錯過什麼？

Answer 1

的差別只是太小，用肉眼看，在這個規模：

使用您的堆排序結果（達到1000000項600毫秒），這裏是一個O(n)功能（綠色）和O(n log n)功能（紅） ： （從http://fooplot.com/plot/gnbb0vdgno）

在這張照片的兩個功能是：

• y = 600/1000000 * x^綠色
• y = 1/(10000 log(10)) * x*log(x)^紅色

（請注意，這些功能有很大的不同恆定的縮放因素，但當然，這些並不在大O符號無所謂。）

但是僅僅是因爲他們很難在圖表中看到，並不意味着它們無法區分。

正如評論中所提到的，您的主要選項是較大的數據集或較慢的比較函數。大多數排序算法將允許您指定一個比較函數，在正常情況下，它不應該改變O（）時間複雜度。 （但要小心非傳遞式比較函數）

如果這是不可能的，並且您只是想將算法作爲黑盒函數，那麼您可以簡單地重複實驗並對結果進行平均，直到噪聲足夠低以區分這兩條曲線。

能得到相應的「理想」 N日誌N曲線與平均數據比較，你需要解決的方程y = a*x * log(x); y=MAXIMUM_TIME; x=MAXIMUM_INPUT_LENGTH;，例如用Wolfram Alpha

---

很重要的一點這裏要說的是，即使這些曲線看起來相似，但這並不意味着假設的線性排序算法的運行時間對於少於一百萬個條目是不值得的。如果你設法拿出一個線性與作爲n爲log N算法相同常數因子排序算法，該曲線是這樣的：