为什么 O(n) 比 O( nlog(n) ) 更好？

Question

我刚刚发现了这个奇怪的发现，在普通数学中，n*logn 会小于 n，因为 log n 通常小于 1。 那么为什么 O(nlog(n)) 大于 O(n) 呢？ （即为什么nlogn被认为比n花费更多的时间）

Big-O 遵循不同的系统吗？

Answer 1

事实证明，我误解了Logn小于1。 当我问了几位前辈后，我今天才知道，如果 n 的值很大（通常是这样，当我们考虑大 O，即最坏情况时），logn 可以大于 1。

所以是的， O(1) < O(logn) < O(n) < O(nlogn) holds true.

（我认为这是一个愚蠢的问题，也打算删除它，但后来意识到，没有问题是愚蠢的问题，可能还有其他人感到困惑，所以我把它留在这里。）

Answer 2

这是流行时间复杂度的图表 \

对于 n>2（对数以 2 为底），O(n*log(n)) 明显大于 O(n)

一个简单的记住方法可能是举两个例子

1. 想象一下二分搜索算法的时间复杂度为 Log N： O(log(N))
2. 如果对于二分查找的每一步，你都必须迭代 N 个元素的数组
3. 该任务的时间复杂度为 O(N*log(N))
4. 这比迭代一次数组需要更多工作：O(N)

Answer 3

...因为 log n 始终小于 1。

这是一个错误的前提。事实上，对于所有 _{n > b}，logb n > 1。例如，log₂ 32 = 5.

通俗地说，您可以将 log n 视为 n 中的位数。如果 n 是 8 位数字，则 log n ≈ 8。对于大多数 n 值，对数通常大于 1，因为 大多数 数字都有多个数字。

Answer 4

绘制两个图表（在 desmos (https://www.desmos.com/calculator) 或任何其他网络上）并查看大 n 值 ( y=f(n)) 的结果。我是说你应该寻找较大的值，因为对于较小的 n 值，程序不会出现时间问题。为了方便起见，我在下面附上了一张图表，您可以尝试使用其他日志基础。

红色代表时间 = n，蓝色代表时间 = nlog(n)。

Answer 5

在计算机中，它是以 2 为底的 log，而不是以 10 为底。因此 log(2) 是 1，log(n)（其中 n>2）是大于 1 的正数。 仅在 log (1) 的情况下，我们的值小于 1，否则，它大于 1。

Answer 6

如果 n 大于 b，则 Log(n) 可以大于 1。但这并不能回答你的问题：为什么 O(n*logn) 大于 O(n)。

通常底数小于 4。因此，对于较高的值 n，n*log(n) 会大于 n。这就是为什么 O(nlogn) > O(n)。

Answer 7

这张图可能会有所帮助。 log (n) 的上升速度比 n 快，并且当 n 大于对数的底数时，log (n) 大于 1。 https://stackoverflow.com/a/7830804/11617347

Answer 8

无论两个函数在

n

值较小时表现如何，当

n

足够大时，它们都会相互比较。理论上，存在一个

N

，对于每个给定的

n > N

，则有

nlogn >= n

。如果您选择

N=10

，则

nlogn

始终大于

n

。

Answer 9

这种说法并不总是准确的。当n较小时，(n^2)比(log n)需要更多时间，但当n较大时，(log n)更有效。对于小值，(n^2) 的增长率小于 (n) 和 (log n)，因此我们可以说 (n^2) 更有效，因为它比 (log n) 花费的时间更少，但是n 增加，(n^2) 急剧增加，而 (log n) 的增长率小于 (n^2) 和 (n)，因此 (log n) 效率更高。

Answer 10

对于较高的 log n 值，它会大于 1。当我们考虑 n 的所有可能值时，我们可以说在大多数情况下 log n 大于 1。因此我们可以说 O(nlogn) > O(n) （假设更高的值）

Answer 11

记住“大O”与值无关，它与函数的形状有关我可以拥有一个运行速度更快的O(n2)函数，即使对于超过一百万的n值也比O(1)函数...

Answer 12

O(1) 表示恒定的时间复杂度。复杂度为 O(1) 的运算 无论输入大小如何，都会以恒定的时间执行。

O(logn) 表示对数时间复杂度。它生长 与输入大小成对数。

O(n) 表示线性时间复杂度。复杂度为 O(n) 的运算 随着输入的大小线性增长。

O(nlogn) 表示线性时间复杂度。它生长于 与 nlogn 的比例，其中 n 是输入的大小。

O(1)