algorithm - 为什么插入排序的 O(n) nlogn 运行时间是最理想的？

Question

我们在类里面学习到插入排序是 omega 线性运行时间(如果传递的是一个已经排序的数组)和 Big-O O(n^2) 对于所有其他情况。然后我们的教授开始讨论具有“合并排序”方法的插入排序的理想选择，并且理想的是使用合并排序并具有 O (nlogn) 运行时间？他不是一个很清楚的人……根本不是。请您解释一下他的意思!

Answer 1

O(N) 被认为是快的，O(N Log(N)) 是公平的，O(N²) 是慢的。

对于少数元素，你可能不关心。但是想一想对一百万个元素进行排序:时间将与 1000000(比如 1 毫秒)、20000000(20 毫秒)和... 1000000000000(11 周)成正比。

这就是为什么 O(N²) 排序算法经常被避免的原因，因为知道 O(N Log(N)) 在所有情况下都是可能的，而 O(N) 对于某些配置。