为什么 O(n log n) 大于 O(n)？
Why O(n log n) is greater than 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)
相矛盾
big O notation只有一个渐近的意思，即只有n趋于无穷才有意义
例如，O(100000) 的时间复杂度仅意味着您的代码以常数时间运行，这比 O(log n).
渐近地更快（更小）
让我们首先阐明什么是当前上下文中的 Big O 表示法。从 (source) 可以读到：
Big O notation is a mathematical notation that describes the limiting
behavior of a function when the argument tends towards a particular
value or infinity. (..) In computer science, big O notation is used to classify algorithms
according to how their run time or space requirements grow as the
input size grows.
以下说法不准确:
For instance taking n as 1, solving O(n log n) will be O(1 log 1) =
O(0). On the same hand O(n) will be O(1)?
不能简单地执行“O(1 log 1)”，因为 Big O 符号不表示函数，而是表示具有某个渐近上限的 set of functions；可以从 source:
中读到
Big O notation characterizes functions according to their growth
rates: different functions with the same growth rate may be
represented using the same O notation.
通俗地说，在计算机科学 time-complexity and space-complexity 理论中，可以将 Big O 符号视为算法的一种分类，具有与时间和 space 相关的最坏情况，分别。例如，O(n):
An algorithm is said to take linear time/space, or O(n) time/space, if its time/space complexity is O(n). Informally, this means that the running time/space increases at most linearly with the size of the input (source).
和O(n log n)为：
An algorithm is said to run in quasilinear time/space if T(n) = O(n log^k n) for some positive constant k; linearithmic time/space is the case k = 1 (source).
从数学上讲语句
I read that O(n log n) is greater than O(n) (..)
不准确，因为如前所述，Big O 符号表示 set of functions。因此，更准确的说法是 O(n log n) 包含 O(n)。尽管如此，通常这种宽松的措辞通常用于量化（对于最坏情况）一组算法与另一组算法相比在输入大小增加方面的表现。比较两个类算法（例如、O(n log n)和O(n)）而不是
For instance taking n as 1, solving O(n log n) will be O(1 log 1) =
O(0). On the same hand O(n) will be O(1)?
Which actually contradicts 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 log n) 不是 数字 ，甚至不是函数，它 完全 说一个比另一个大是有道理的。这是草率的语言，但实际上有 两个 准确的陈述可能是说“O(n log n) 大于 O(n)”。
首先，对于 n 的任何函数 f(n)，O(f(n)) 是所有渐近增长不快于 f( n).正式的定义是：
A function g(n) is in O(f(n)) if and only if there are constants n0 and C such that g(n) <= Cf(n) for all n > n0.
所以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) 的上限。更具体地说，对于所有 n > n0，存在一个常数 n0 使得 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)”这句话在严格意义上没有任何意义，但如果您愿意慷慨地阅读它，它的含义就会清晰明确。
我读到 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)
big O notation只有一个渐近的意思，即只有n趋于无穷才有意义
例如，O(100000) 的时间复杂度仅意味着您的代码以常数时间运行，这比 O(log n).
让我们首先阐明什么是当前上下文中的 Big O 表示法。从 (source) 可以读到：
Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. (..) In computer science, big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows.
以下说法不准确:
For instance taking n as 1, solving O(n log n) will be O(1 log 1) = O(0). On the same hand O(n) will be O(1)?
不能简单地执行“O(1 log 1)”，因为 Big O 符号不表示函数，而是表示具有某个渐近上限的 set of functions；可以从 source:
Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same
Onotation.
通俗地说，在计算机科学 time-complexity and space-complexity 理论中，可以将 Big O 符号视为算法的一种分类，具有与时间和 space 相关的最坏情况，分别。例如，O(n):
An algorithm is said to take linear time/space, or O(n) time/space, if its time/space complexity is O(n). Informally, this means that the running time/space increases at most linearly with the size of the input (source).
和O(n log n)为：
An algorithm is said to run in quasilinear time/space if T(n) = O(n log^k n) for some positive constant k; linearithmic time/space is the case k = 1 (source).
从数学上讲语句
I read that O(n log n) is greater than O(n) (..)
不准确，因为如前所述，Big O 符号表示 set of functions。因此，更准确的说法是 O(n log n) 包含 O(n)。尽管如此，通常这种宽松的措辞通常用于量化（对于最坏情况）一组算法与另一组算法相比在输入大小增加方面的表现。比较两个类算法（例如、O(n log n)和O(n)）而不是
For instance taking n as 1, solving O(n log n) will be O(1 log 1) = O(0). On the same hand O(n) will be O(1)?
Which actually contradicts 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 log n) 不是 数字 ，甚至不是函数，它 完全 说一个比另一个大是有道理的。这是草率的语言，但实际上有 两个 准确的陈述可能是说“O(n log n) 大于 O(n)”。
首先，对于 n 的任何函数 f(n)，O(f(n)) 是所有渐近增长不快于 f( n).正式的定义是：
A function g(n) is in O(f(n)) if and only if there are constants n0 and C such that g(n) <= Cf(n) for all n > n0.
所以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) 的上限。更具体地说，对于所有 n > n0，存在一个常数 n0 使得 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)”这句话在严格意义上没有任何意义，但如果您愿意慷慨地阅读它，它的含义就会清晰明确。