为什么我们忽略大 O 表示法中的系数？
Why do we ignore co-efficients in Big O notation?
在搜索有关"Big O"符号的答案时，我看到了很多诸如this, this, or this之类的SO答案，但我仍然没有弄清楚一些地方。
为什么我们忽略系数？
例如this answer表示2N + 2的最终复杂度为O(N)；我们也删除了领先系数 2 和最终常数 2。
去掉最后的常量2或许可以理解。毕竟，N 可能非常大，因此 "forgetting" 最后的 2 可能只会将总计改变一小部分。
但是我无法清楚地理解如何删除 leading 系数并没有什么不同。如果上面的前导 2 变成 1 或 3，则总计的百分比变化会很大。
同样，显然 2N^3 + 99N^2 + 500 是 O(N^3)。我们如何忽略 99N^2 和 500？
Big-O 表示法的目的是找出当值趋于无穷大时函数渐近行为的主导因素。
当我们遍历功能域时，一些因素变得比其他因素更重要。
想象一下 f(n) = n^3+n^2。随着 n 趋于无穷大，与 n^3 相比，n^2 变得越来越不相关。
但这只是定义背后的直觉。实际上，由于形式定义，我们忽略了函数的某些部分：
f(x) = O(g(x)) as x->infinity
if and only if there is a positive real M and a real x_0 such as
|f(x)| <= M|g(x)| for all x > x_0.
那是 in wikipedia。这实际上意味着有一个点（在 x_0 之后）之后 g(x) 的某个倍数支配 f(x)。该定义就像 f(x).
值的松散上限
从中我们可以推导出许多其他属性，例如 f(x)+K = O(f(x))、f(x^n+x^n-1)=O(x^n) 等。只需使用定义来证明这些属性即可。
在特殊的中，删除系数（K*f(x) = O(f(x))）背后的直觉在于我们试图用计算复杂度来衡量的东西。归根结底，一切都与时间（或任何资源有关）有关。但是很难知道每个操作需要多少时间。一种算法可能执行 2n 操作，而另一种算法可能执行 n，但后者可能具有与之关联的较大常数时间。因此，出于这个目的，很难推断出 n 和 2n.
之间的区别
对于实际应用，常量 很重要，因此对于 n smaller than 500.[=19 的输入，O(2 n^3) 将优于 O(1000 n^2) =]
这里有两个主要思想：1) 如果你的算法对任何输入都很好，它应该具有低时间复杂度，以及 2) n^3 比 [=15= 增长得快得多]，n^3 而不是 n^2 几乎没有任何意义。
An other thing is that, what I have understood, the complexity of 2N^3 + 99N^2 + 500 will be O(N^3). So how do we ignore/remove 99N^2 portion even? Will it not make difference when let's say N is one miilion?
没错，在这种情况下，99N^2 项 far 被 2N^3 项所掩盖。他们的交叉点是 N=49.5，远小于一百万。
但是你提出了一个很好的观点。事实上，渐近计算复杂性分析经常因忽略常量因素而受到批评，这些常量因素会在实际应用中产生巨大差异。然而，big-O 仍然是一个有用的工具，可以在几个音节中捕获算法的效率。通常情况下，n^2 算法在现实生活中比 n^3 算法对于非平凡 n 算法更快，并且 log(n) 算法几乎总是这样比 n^2 算法快得多。
除了作为近似实际效率的便捷标尺外，它还是算法复杂度理论分析的重要工具。许多有用的属性来自多项式的可组合性——这是有道理的，因为嵌套循环是计算的基础，并且它们对应于多项式的步数。使用渐近复杂性分析，您可以证明 a rich set 不同类别算法之间的关系，这可以告诉我们解决某些问题的效率究竟有多高。
从（复杂性）理论的角度来看，系数代表我们可以忽略的硬件细节。具体来说，Linear Speedup Theorem 规定对于任何问题，我们总是可以在计算机上投入呈指数增长的硬件（金钱）数量，以获得速度的线性提升。
因此，模数昂贵的硬件购买解决同一问题的两种算法，对于所有输入大小，一种算法的速度是另一种算法的两倍，被认为本质上是相同的。
Big-O (Landau) 表示法独立地起源于数论，它的一个用途是在函数之间创建一种等价：如果给定函数在另一个函数上方有界，同时在下方有界同一个其他函数的缩放版本，那么从渐近的角度来看，这两个函数本质上是相同的。 Big-O（实际上是"Big-Theta"）的定义抓住了这种情况：两个函数的"Big-O"（Theta）正好相等。
事实上，Big-O 符号允许我们在比较函数增长时忽略主要常数，这使得 Big-O 成为衡量算法各种质量的理想工具，同时尊重（忽略）"freebie" 优化由线性加速定理提供。
Big O 提供了一个很好的估计，即在所有条件都相同的情况下，哪些算法对于更大的输入更有效；这就是为什么对于具有 n^3 和 n^2 因子的算法，我们忽略 n^2 因子，因为即使 n^2 因子具有很大的常数，它最终也会被 n^3 因子支配。
然而，真正的算法包含的不仅仅是简单的大 O 分析，例如排序算法通常会从 O(n * log(n)) 分区算法开始，如快速排序或归并排序，当分区变得足够小时该算法将切换到更简单的 O(n^2) 算法，如插入排序——对于小输入，插入排序通常更快，尽管基本的大 O 分析没有揭示这一点。
常量因子通常不是很有趣，因此它们被省略了 - 当然，1000 数量级的因子差异很有趣，但通常因子差异更小，然后还有更多要考虑的常量因素可能支配算法的常量。假设我有两种算法，第一种算法使用 运行ning 时间 3*n，第二种算法使用 运行ning 时间 2*n，每个算法都具有可比较的 space 复杂度。此分析假设统一的内存访问；如果第一个算法与缓存的交互更好，并且这足以弥补更差的常数因子怎么办？如果可以对它应用更多的编译器优化，或者它在内存管理子系统中表现得更好，或者需要更便宜的 IO（例如更少的磁盘寻道或更少的数据库连接等等）等等，会怎么样？算法的常数因子是相关的，但还有更多的常数需要考虑。通常，确定哪种算法最好的最简单方法就是 运行 对某些样本输入和计算结果进行计时；过度依赖算法的常数因子会隐藏这一步。
数学原因：
我们这样做的真正原因是 Big O-Notation 的定义方式：
当系列 f(n)/g(n) 有界时，系列（或让我们使用函数一词）f(n) 在 O(g(n)) 中。示例：
f(n)= 2*n^2
g(n)= n^2
f(n) 在 O(g(n)) 中，因为 (2*n^2)/(n^2) = 2 随着 n 接近无穷大。 (2*n^2)/(n^2) 项不会变得无限大（它始终为 2），因此商是有界的，因此 2*n^2 在 O(n^2) 中。
另一个：
f(n) = n^2
g(n) = n
随着 n 趋于无穷大，n^2/n (= n) 项变得无限大，因此 n^2 不在 O(n) 中。
同样的原则适用，当你有
f(n) = n^2 + 2*n + 20
g(n) = n^2
(n^2 + 2*n + 20)/(n^2) 也是有界的，因为随着 n 趋于无穷大，它趋于 1。
Big-O Notation 基本上描述了函数 f(n)（从 n 的某个值到无穷大）小于函数 g(n)，乘以一个常数。对于前面的例子：
2*n^2在O(n^2)中，因为我们可以找到一个值C，所以2*n^2小于C*n^2。在这个例子中，我们可以选择C为5或10，例如，满足条件。
那么你从中得到了什么？如果您知道您的算法的复杂度为 O(10^n) 并且您输入了一个包含 4 个数字的列表，那么它可能只需要很短的时间。如果您输入 10 个数字，将花费一百万倍的时间！如果它长 100 万倍或 500 万倍在这里并不重要。您总是可以再使用 5 台计算机并在相同的时间内拥有它 运行，这里真正的问题是，它随着输入大小的扩展非常糟糕。
大 O 表示法不是复杂性的绝对度量。
而是表示随着变量的变化，复杂性将如何变化。换句话说，随着 N 的增加，复杂度会增加
大 O(f(N)).
为了解释为什么不包括条款，我们看看条款增加的速度。
所以，Big O(2n+2) 有两项 2n 和 2。看增长率
Big O(2) 这一项永远不会增加，它根本不会影响增长率，所以它消失了。此外，由于 2n 的增长速度比 2 快，因此当 n 变得非常大时，2 会变成噪声。
类似Big O(2n^3 + 99n^2)比较Big O(2n^3)和Big O(99n^2)。对于较小的值，比如 n < 50，99n^2 将贡献比 2n^3 更大的标称百分比。然而，如果 n 变得非常大，比如 1000000，那么 99n^2 虽然名义上很大，但与 2n^3 的大小相比是微不足道的（接近百万分之一）。
因此大 O(n^i) < 大 O(n^(i+1))。
由于大 O 的数学定义，系数被删除。
为了简化定义，大 O(f(n)) = 大 O(f(cn)) 对于常量 c。这需要相信，因为这样做的原因纯粹是数学上的，因此证明太复杂和枯燥，无法用简单的术语来解释。
在搜索有关"Big O"符号的答案时，我看到了很多诸如this, this, or this之类的SO答案，但我仍然没有弄清楚一些地方。
为什么我们忽略系数？
例如this answer表示2N + 2的最终复杂度为O(N)；我们也删除了领先系数 2 和最终常数 2。
去掉最后的常量2或许可以理解。毕竟，N 可能非常大，因此 "forgetting" 最后的 2 可能只会将总计改变一小部分。
但是我无法清楚地理解如何删除 leading 系数并没有什么不同。如果上面的前导 2 变成 1 或 3，则总计的百分比变化会很大。
同样，显然 2N^3 + 99N^2 + 500 是 O(N^3)。我们如何忽略 99N^2 和 500？
Big-O 表示法的目的是找出当值趋于无穷大时函数渐近行为的主导因素。
当我们遍历功能域时，一些因素变得比其他因素更重要。
想象一下 f(n) = n^3+n^2。随着 n 趋于无穷大，与 n^3 相比，n^2 变得越来越不相关。
但这只是定义背后的直觉。实际上，由于形式定义，我们忽略了函数的某些部分：
f(x) = O(g(x))asx->infinityif and only if there is a positive real
Mand a realx_0such as
|f(x)| <= M|g(x)|for allx > x_0.
那是 in wikipedia。这实际上意味着有一个点（在 x_0 之后）之后 g(x) 的某个倍数支配 f(x)。该定义就像 f(x).
从中我们可以推导出许多其他属性，例如 f(x)+K = O(f(x))、f(x^n+x^n-1)=O(x^n) 等。只需使用定义来证明这些属性即可。
在特殊的中，删除系数（K*f(x) = O(f(x))）背后的直觉在于我们试图用计算复杂度来衡量的东西。归根结底，一切都与时间（或任何资源有关）有关。但是很难知道每个操作需要多少时间。一种算法可能执行 2n 操作，而另一种算法可能执行 n，但后者可能具有与之关联的较大常数时间。因此，出于这个目的，很难推断出 n 和 2n.
对于实际应用，常量 很重要，因此对于 n smaller than 500.[=19 的输入，O(2 n^3) 将优于 O(1000 n^2) =]
这里有两个主要思想：1) 如果你的算法对任何输入都很好，它应该具有低时间复杂度，以及 2) n^3 比 [=15= 增长得快得多]，n^3 而不是 n^2 几乎没有任何意义。
An other thing is that, what I have understood, the complexity of 2N^3 + 99N^2 + 500 will be O(N^3). So how do we ignore/remove 99N^2 portion even? Will it not make difference when let's say N is one miilion?
没错，在这种情况下，99N^2 项 far 被 2N^3 项所掩盖。他们的交叉点是 N=49.5，远小于一百万。
但是你提出了一个很好的观点。事实上，渐近计算复杂性分析经常因忽略常量因素而受到批评，这些常量因素会在实际应用中产生巨大差异。然而，big-O 仍然是一个有用的工具，可以在几个音节中捕获算法的效率。通常情况下，n^2 算法在现实生活中比 n^3 算法对于非平凡 n 算法更快，并且 log(n) 算法几乎总是这样比 n^2 算法快得多。
除了作为近似实际效率的便捷标尺外，它还是算法复杂度理论分析的重要工具。许多有用的属性来自多项式的可组合性——这是有道理的，因为嵌套循环是计算的基础，并且它们对应于多项式的步数。使用渐近复杂性分析，您可以证明 a rich set 不同类别算法之间的关系，这可以告诉我们解决某些问题的效率究竟有多高。
从（复杂性）理论的角度来看，系数代表我们可以忽略的硬件细节。具体来说，Linear Speedup Theorem 规定对于任何问题，我们总是可以在计算机上投入呈指数增长的硬件（金钱）数量，以获得速度的线性提升。
因此，模数昂贵的硬件购买解决同一问题的两种算法，对于所有输入大小，一种算法的速度是另一种算法的两倍，被认为本质上是相同的。
Big-O (Landau) 表示法独立地起源于数论，它的一个用途是在函数之间创建一种等价：如果给定函数在另一个函数上方有界，同时在下方有界同一个其他函数的缩放版本，那么从渐近的角度来看，这两个函数本质上是相同的。 Big-O（实际上是"Big-Theta"）的定义抓住了这种情况：两个函数的"Big-O"（Theta）正好相等。
事实上，Big-O 符号允许我们在比较函数增长时忽略主要常数，这使得 Big-O 成为衡量算法各种质量的理想工具，同时尊重（忽略）"freebie" 优化由线性加速定理提供。
Big O 提供了一个很好的估计，即在所有条件都相同的情况下，哪些算法对于更大的输入更有效；这就是为什么对于具有 n^3 和 n^2 因子的算法，我们忽略 n^2 因子，因为即使 n^2 因子具有很大的常数，它最终也会被 n^3 因子支配。
然而，真正的算法包含的不仅仅是简单的大 O 分析，例如排序算法通常会从 O(n * log(n)) 分区算法开始，如快速排序或归并排序，当分区变得足够小时该算法将切换到更简单的 O(n^2) 算法，如插入排序——对于小输入，插入排序通常更快，尽管基本的大 O 分析没有揭示这一点。
常量因子通常不是很有趣，因此它们被省略了 - 当然，1000 数量级的因子差异很有趣，但通常因子差异更小，然后还有更多要考虑的常量因素可能支配算法的常量。假设我有两种算法，第一种算法使用 运行ning 时间 3*n，第二种算法使用 运行ning 时间 2*n，每个算法都具有可比较的 space 复杂度。此分析假设统一的内存访问；如果第一个算法与缓存的交互更好，并且这足以弥补更差的常数因子怎么办？如果可以对它应用更多的编译器优化，或者它在内存管理子系统中表现得更好，或者需要更便宜的 IO（例如更少的磁盘寻道或更少的数据库连接等等）等等，会怎么样？算法的常数因子是相关的，但还有更多的常数需要考虑。通常，确定哪种算法最好的最简单方法就是 运行 对某些样本输入和计算结果进行计时；过度依赖算法的常数因子会隐藏这一步。
数学原因：
我们这样做的真正原因是 Big O-Notation 的定义方式： 当系列 f(n)/g(n) 有界时，系列（或让我们使用函数一词）f(n) 在 O(g(n)) 中。示例：
f(n)= 2*n^2
g(n)= n^2
f(n) 在 O(g(n)) 中，因为 (2*n^2)/(n^2) = 2 随着 n 接近无穷大。 (2*n^2)/(n^2) 项不会变得无限大（它始终为 2），因此商是有界的，因此 2*n^2 在 O(n^2) 中。
另一个：
f(n) = n^2
g(n) = n
随着 n 趋于无穷大，n^2/n (= n) 项变得无限大，因此 n^2 不在 O(n) 中。
同样的原则适用，当你有
f(n) = n^2 + 2*n + 20
g(n) = n^2
(n^2 + 2*n + 20)/(n^2) 也是有界的，因为随着 n 趋于无穷大，它趋于 1。
Big-O Notation 基本上描述了函数 f(n)（从 n 的某个值到无穷大）小于函数 g(n)，乘以一个常数。对于前面的例子：
2*n^2在O(n^2)中，因为我们可以找到一个值C，所以2*n^2小于C*n^2。在这个例子中，我们可以选择C为5或10，例如，满足条件。
那么你从中得到了什么？如果您知道您的算法的复杂度为 O(10^n) 并且您输入了一个包含 4 个数字的列表，那么它可能只需要很短的时间。如果您输入 10 个数字，将花费一百万倍的时间！如果它长 100 万倍或 500 万倍在这里并不重要。您总是可以再使用 5 台计算机并在相同的时间内拥有它 运行，这里真正的问题是，它随着输入大小的扩展非常糟糕。
大 O 表示法不是复杂性的绝对度量。
而是表示随着变量的变化，复杂性将如何变化。换句话说，随着 N 的增加，复杂度会增加 大 O(f(N)).
为了解释为什么不包括条款，我们看看条款增加的速度。
所以，Big O(2n+2) 有两项 2n 和 2。看增长率 Big O(2) 这一项永远不会增加，它根本不会影响增长率，所以它消失了。此外，由于 2n 的增长速度比 2 快，因此当 n 变得非常大时，2 会变成噪声。
类似Big O(2n^3 + 99n^2)比较Big O(2n^3)和Big O(99n^2)。对于较小的值，比如 n < 50，99n^2 将贡献比 2n^3 更大的标称百分比。然而，如果 n 变得非常大，比如 1000000，那么 99n^2 虽然名义上很大，但与 2n^3 的大小相比是微不足道的（接近百万分之一）。
因此大 O(n^i) < 大 O(n^(i+1))。
由于大 O 的数学定义，系数被删除。
为了简化定义，大 O(f(n)) = 大 O(f(cn)) 对于常量 c。这需要相信，因为这样做的原因纯粹是数学上的，因此证明太复杂和枯燥，无法用简单的术语来解释。