为什么O(n log n)大于O(n)？

Question

我读到过O(n log n)比O(n)大，我需要知道为什么？

例如，当n等于1时，解决O(n log n)将是O(1 log 1) = O(0)。另一方面，O(n)将是O(1)？

这实际上与O(n log n) > O(n)相矛盾。

- user14673850

Answer 1

让我们首先澄清当前背景下的“大O符号”是什么。可以从（source）中读到以下内容：

引用： 大O符号是一种数学符号，描述了函数在参数趋向于特定值或无穷大时的极限行为。（..）在计算机科学中，大O符号用于根据输入大小增长时算法的运行时间或空间需求来分类。

以下陈述不准确：

引用： 例如，将n视为1，解决O(n log n)将是O(1 log 1)= O(0)。同样，O(n)将是O(1)吗？

不能简单地执行“O(1 log 1)” ，因为大O符号并不表示一个函数，而是具有某个渐近上界的一组函数; 可以从source中读到：

引用： 大O符号根据其增长速度表征函数：具有相同增长速率的不同函数可以使用相同的O符号表示。

非正式地说，在计算机科学的时间复杂度和空间复杂度理论中，人们可以将大O符号视为关于时间和空间最坏情况的算法分类。例如，O(n)：

引用： 如果算法的时间/空间复杂度为O(n)，则称算法具有线性时间/空间或O(n)时间/空间。非正式地说，这意味着运行时间/空间最多随输入大小线性增加（source）。

而O(n log n)则为：

引用： 如果T(n)= O(n log^k n)对于某个正常数k成立，则称算法在准线性时间/空间下运行; 如果k = 1，则是线性时间/空间（source）。

从数学上讲，陈述如下：

引用： 我读到O(n log n)大于O(n)（..）

这句话不准确，因为正如之前提到的，Big O符号表示一组函数集合。更准确的说法是O(n log n)包含O(n)。然而，通常这样放松措辞是用来量化（针对最坏情况）一组算法相对于另一组算法在其输入尺寸增加时行为的方式。要比较两类算法（例如，O(n log n)和O(n)），而不是

例如，取n=1时，求解O(n log n)将得到O(1 log 1)=O(0)。与此同时，O(n)将得到O(1)?

这实际上与O(n log n)>O(n)相矛盾

你应该分析两类算法在它们的输入大小（即n）在最坏情况下的行为方式；分析当n趋近于无穷大时。

正如@cem所指出的，在图像中"big-O表示绘制函数的渐进最小上界之一，并不是指集合O(f(n))"

您可以看到，在某个输入后，O(n log n)（绿线）比O(n)（黄线）增长得更快。这就是为什么（对于最坏情况）O(n)比O(n log n)更可取的原因，因为人们可以增加输入大小，前者的增长速度比后者慢。

- dreamcrash

Answer 2

我将给你提供一个真正的答案，即使它似乎比你目前的思考方式更复杂...

O(n)和O(n log n)不是数字，甚至不是函数，说其中一个大于另一个不太合理。虽然这种语言有些粗糙，但实际上说"O(n log n) 大于 O(n)"可能有两个准确的意思。

首先，对于任何n的函数f(n)，O(f(n))都是渐近增长速度不能超过f(n)的所有函数的无限集合。一个正式的定义是：

如果存在常量n0和C，使得对于所有n > n0都有g(n) <= Cf(n)，那么函数g(n)就属于O(f(n))。

所以，O(n)是一组函数，O(n log n)也是一组函数，而O(n log n)是O(n)的超集。成为一个超集有点像是"更大"，因此，如果有人说"O(n log n) 大于 O(n)"，他们可能是指它们之间的超集关系。

其次，O(f(n))的定义使得f(n)成为该集合中函数渐近增长的一个上界。对于O(n log n)和O(n)，前者的上界要大于后者。更具体地说，存在常量n0，对于所有大于n0的n，n log n > n。这个边界函数本身是渐近更大的，这也是说“O(n log n)比O（n）更大”可能意味着的另一件事。

最后，这两个说法在数学上是等价的。如果g(n)在渐近意义下大于f(n)，则在数学上有O(g(n))是O(f(n))的超集，如果O(g(n))是O(f(n))的真超集，则在数学上有g(n)在渐近意义下大于f(n)。

因此，尽管“O(n log n)比O(n)更大”这种说法严格来讲没有任何意义，但如果你愿意通情达理地阅读它，它就有一个清晰明确的含义。

- Matt Timmermans

Answer 3

大 O 符号只有渐进意义，即只有当 n 趋近无穷大时才有意义。

例如，时间复杂度为 O(100000) 仅表示你的代码在常量时间内运行，渐进上更快（更小）比O(log n) 更快。

- Thibault D.