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

让我们首先澄清Big O当前上下文中什么是符号。从（来源）可以阅读：

Big O 表示法是一种数学表示法，它描述了当参数趋向于特定值或无穷大时函数的限制行为。(..)在计算机科学中，大 O 符号用于根据算法的运行时间或空间要求随着输入大小的增长而增长的情况进行分类。

以下说法不准确：

例如取 n 为 1，求解 O(n log n) 将是 O(1 log 1) = O(0)。同样，O(n) 将是 O(1)？

不能简单地执行“O(1 log 1)”，因为该Big O符号不代表一个函数，而是一组具有某个渐近上限的函数；正如人们可以从源代码中读取的那样：

Big O 表示法根据函数的增长率来表征函数：具有相同增长率的不同函数可以使用相同的O表示法来表示。

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

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

并O(n log n)作为：

对于某个正常数 k，如果 T(n) = O(n log^kn)，则称算法在拟线性时间/空间中运行；线性时间/空间是 k = 1 ( source ) 的情况。

从数学上讲这个陈述

我读到 O(n log n) 大于 O(n) (..)

不准确，因为如前所述，Big O符号表示一组函数。因此，更准确的是O(n log n)contains 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)增加输入规模更可取的原因，前者的增长率比后者慢。

我将给你真正的答案，即使它似乎与你目前的想法相差不止一步……

O（n）和O（N日志N）不是数字，甚至是功能，和它不会很有道理地说，一个比另一个更大。这是草率的语言，但实际上有两个准确的陈述可能是说“O（n log n）大于O（n）”。

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

当且仅当存在常数 n0 和 C 使得 g(n) <= Cf(n) 对于所有 n > n0 时，函数 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 使得 n log n > n，对于所有 n > n0。边界函数本身渐近地更大，这是人们在说“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)”这句话在严格意义上没有任何意义，但如果您愿意仁慈地阅读它，它具有清晰明确的含义。

在大O表示法只有一个渐近的含义，即它只有时才有意义n趋于无穷大。

例如，时间复杂度O(100000)仅意味着您的代码在恒定时间内运行，这比 渐近地更快（更小）O(log n)。