插入排序/堆排序时间复杂度

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)算法，但它会采取一比你计算的时间多得多。