为什么 O(n) 比 O( nlog(n) ) 好？
Rit*_*eak 24 algorithm big-o time-complexity data-structures
我刚刚发现这个奇怪的发现，在正常数学中，n*logn 会小于 n，因为 log n 通常小于 1。那么为什么 O(nlog(n)) 大于 O(n)？（即为什么 nlogn 被认为比 n 花费更多的时间）
Big-O 是否遵循不同的系统？
Rit*_*eak 58
事实证明，我误解了 Logn 小于 1。正如我问过的几个前辈我今天自己才知道的，如果 n 的值很大，（通常是这样，当我们考虑 Big O ie最坏的情况），logn 可以大于 1。
所以是的， O(1) < O(logn) < O(n) < O(nlogn) 成立。
（我认为这是一个愚蠢的问题，也正要删除它，但后来意识到，没有问题是愚蠢的问题，可能还有其他人对此感到困惑，所以我把它留在这里。）
- 这根本不是一个愚蠢的问题！到现在为止我一直对此感到困惑。看来关键是‘基础’。 (7认同)
Cal*_*ary 34
这是流行时间复杂度的图表 \
对于 n>2（对数以 2 为底），O(n*log(n)) 明显大于 O(n)
一个简单的记住方法可能是举两个例子
- 想象一下二分搜索算法的时间复杂度为 Log N：O(log(N))
- 如果对于二分查找的每一步，您都必须迭代 N 个元素的数组
- 该任务的时间复杂度为O(N*log(N))
- 这比迭代一次数组需要更多的工作：O(N)
Joh*_*ica 19
...因为 log n 总是小于 1。
这是一个错误的前提。事实上，对于所有n > b，log b n > 1 。例如，日志2 32 = 5。
通俗地说，你能想到的日志ñ作为在数字位数ñ。如果n是 8 位数字，则记录n ? 8.对于大多数n值，对数通常大于 1 ，因为大多数数字都有多个数字。
绘制图形（在 desmos ( https://www.desmos.com/calculator ) 或任何其他网络上）并在 n 的大值（ y=f(n) ）上查看自己的结果。我是说你应该寻找大值，因为对于小值 n 程序不会有时间问题。为方便起见，我在下面附上了一张图表，您可以尝试使用其他日志基础。
红色代表时间 = n，蓝色代表时间 = nlog(n)。
在计算机中，它是以 2 为底的 log，而不是以 10 为底。因此 log(2) 是 1，log(n)（其中 n>2）是大于 1 的正数。仅在 log (1) 的情况下，我们的值小于 1，否则它大于 1。
如果 n 大于 b，则 Log(n) 可以大于 1。但这并不能回答您的问题：为什么 O(n*logn) 大于 O(n)。
通常基数小于 4。因此，对于较高的值 n，n*log(n) 会大于 n。这就是为什么 O(nlogn) > O(n)。