在寻找与“Big O”符号相关的答案时，我看到了很多SO答案，例如this https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it, this https://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o/487278#487278, or this https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm，但我还是没有清楚地理解一些点。
为什么我们忽略系数？
例如这个答案 https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm说最终的复杂度2N + 2 is O(N);我们删除首项系数2和最终常数2以及。
删除最终常数2也许可以理解。毕竟，N可能非常大，所以“忘记”了最后的2可能只会改变总数的一小部分。
但是我无法清楚地理解如何删除leading系数没有区别。如果领先2上面就变成了1 or a 3，总计的百分比变化将会很大。
同样，显然2N^3 + 99N^2 + 500 is O(N^3)。我们如何忽略99N^2随着500?
Big-O 表示法的目的是找出当函数的值趋于无穷大时，函数渐近行为的主导因素是什么。
当我们遍历函数域时，某些因素变得比其他因素更重要。
Imagine f(n) = n^3+n^2. As n趋于无穷大，n^2与相比变得越来越不相关n^3.
但这只是定义背后的直觉。在实践中，由于形式定义，我们忽略了函数的某些部分：
f(x) = O(g(x)) as x->infinity
当且仅当存在正实数M和一个真实的x_0 such as
|f(x)| <= M|g(x)|对全部x > x_0.
That's 在维基百科中 http://en.wikipedia.org/wiki/Big_O_notation。这实际上意味着有一个点（之后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 and 2n.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
