插入排序/堆排序時間複雜度

Question

假設您必須使用n = 1,000,000元素對數組進行排序。插入sort和heapsort需要多長時間，假設每個基本步驟需要1毫秒？

---

我知道，插入排序在最壞的情況下n^2步驟，堆排序在最壞的情況下n log n步驟。

因此，對於插入排序1,000,000^2 = 1*10^12毫秒

和1,000,000 * log(1,000,000)爲堆排序？ 6,000,000毫秒

是否正確？

Answer 1

嗯......

的問題是，「訂單」符號只是說說限制和比較，而不是絕對時間。它也留下了常數和低階項。

例如（這完全是虛構的），實際運行時間，你可能會看具體的插入排序的實現可能是：

num steps = 45,334 * n^2 + 6,500,000 * n + 2,000,000 

這是一個O(n^2)算法，但它會採取一比你計算的時間多得多。