在 Coursera 上的普林斯顿教程中，讲师解释了常见的增长函数。他说线性和线性算术运行时间是“我们所追求的”，他的理由是随着输入大小的增加，运行时间也会增加。我认为这是他犯了错误的地方，因为我之前听他提到线性增长顺序对于高效算法来说并不令人满意。
在他讲话的同时，他还展示了一张绘制不同运行时间的图表 - 常数和对数运行时间看起来效率更高。那么这是一个错误还是真的？
最佳答案
在上下文中认为 O(n) 和 O(n log n) 函数比 O(1) 和 O(log n) 函数具有更好的复杂性是错误的。在查看大 O 表示法中复杂性的典型案例时:
O(1) < O(log n) < O(n) < O(n log n) < O(n^2)
请注意，这并不一定意味着它们在性能方面总是更好 - 我们可以有一个 O(1) 函数，它需要很长时间才能执行，即使它的复杂性不受元素数量的影响。这样的函数在大 O 表示法中看起来比 O(log n) 函数更好，但实际上在实践中可能表现更差。
一般来说:当 n 足够高时，复杂度较低的函数(大 O 表示法)将胜过复杂度较高的函数(大 O 表示法)。
关于algorithm - n 或 nlog(n) 是否优于常数或对数时间？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25899249/