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

Question

假设您必须使用n = 1,000,000元素对数组进行排序。假设每一个基本步骤都需要100秒，那么插入排序和堆排序大概需要多长时间？

我知道插入排序在最坏的情况下采取n^2步骤，而堆排序在最坏的情况下采取n log n步骤。

所以1,000,000 ^ 2用于插入排序= 1*10^12毫秒

1,000,000 * log(1,000,000)表示堆排序？6,000,000 milli-秒

是这样吗？

Answer 1

好吧..。

问题是，“顺序”符号只是在谈论极限和比较，而不是绝对的时间。它还保留了常数和低阶项。

例如(这完全是虚构的)，您可能正在查看的特定插入排序实现的实际运行时间可能是：

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

这是一个O(n^2)算法，但它将花费比您计算的时间多得多的时间。