为什么我们忽略共同efficients在大O符号？ [英] Why do we ignore co-efficients in Big O notation?
问题描述
虽然搜索大O符号的答案我用Google搜索了很多，也看到了很多让喜欢的链接1 ，<一个href="http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o/487278#487278">link 2 ，链接3 更多的人，但我仍然没有清楚地理解一些问题。
While searching for an answer of Big O Notation I have googled a lot and have also seen many SO answers like link 1, link 2, link 3 and many more, but still I have not clearly understood some points.
其中之一是为什么我们忽略/删除共同efficients？
例如在 2N + 2 将 O（N）（指除去恒2也是合作效率2）。
For example in one answer given in this link, it is said that final complexity of 2N + 2 will be O(N) (means we remove the constant 2 and also the co-efficient 2).
确定，删除常量2不作那么多不同，在同一行的回答说设N为一百万。然后，第一项是2万元，第二项是只有2 ，以便消除2不会相差太大，但我不能清楚地了解如何去除合作效率不使差？无合作效率它为一百万和与共同有效的是2百万，装置两次，并且，如果所述合作效率为9，（意味着将9百万）或任何更大的价值呢？
OK, removing constant 2 does not make that much different as in one line the answer says Suppose N is a million. Then the first term is 2 million and the second term is only 2 so removing 2 does not make that much difference, but I cannot clearly understand how removing the co-efficient does not make difference? Without co-efficient it is one million and with co-efficient is 2 millions, means twice, and what if the co-efficient is 9, (means it will be 9 millions) or any larger value?
这是另一件事是，我所理解的， 2N ^ 3 + 99N ^ 2 + 500 将 0的复杂性（N ^ 3）。那么，我们如何忽略/偶删除 99N ^ 2 部分？它会不会使差异，当假设N为1 miilion？
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?
请深入浅出的讲解。
[对不起，如果这个问题似乎是愚蠢的，因为我是新来的分析 - - 算法]
[Sorry, if the question seems to be silly, because I am new to analysis-of-Algorithms]
推荐答案
大O符号的目的是要找到什么是函数的渐近行为的主导因素为价值趋向无穷大。
The purpose of the Big-O notation is to find what is the dominant factor in the asymptotic behavior of a function as the value tends towards the infinity.
当我们通过功能域走，有些因素变得更为重要。
As we walk through the function domain, some factors become more important than others.
想象 F（N）= N ^ 3 + N ^ 2 。由于 N 趋于无穷大， N ^ 2 变得越来越少有关与相比，当n ^ 3 。
Imagine f(n) = n^3+n^2. As n goes to infinity, n^2 becomes less and less relevant when compared with n^3.
不过，这仅仅是定义背后的直觉。在实践中我们忽略功能的，因为在正式定义的一些部分：
But that's just the intuition behind the definition. In practice we ignore some portions of the function because of the formal definition:
F（X）= O（G（X））为 X-＆GT;无限
当且仅当有一个正实 M 和一个真正的 X_0 等
if and only if there is a positive real M and a real x_0 such as
| F（X）| ＆LT; = M | G（X）| 所有
这是在维基百科。这实际上意味着，有一点（在 X_0 ）之后的 G（x）占主导地位的一些多函数f（x）。这个定义的行为像一个松散的上界 F的值（x）。
That's in wikipedia. What that actually means is that there is a point (after x_0) after which some multiple of g(x) dominates f(x). That definition acts like a loose upper bound on the value of f(x).
这是我们可以得到许多其他属性，如 F（X）+ K = O（F（X））， F（X ^ N + X ^ N-1）= O（X ^ N）等，这是一个使用的定义来证明这些只是早晚的问题。
From that we can derive many other properties, like f(x)+K = O(f(x)), f(x^n+x^n-1)=O(x^n), etc. It's just a matter of using the definition to prove those.
在特殊的背后取下系数的直觉（ K * F（X）= O（F（X）））位于我们尝试与计算复杂度来衡量。最终它是所有关于时间（或任何资源，实际上）。但它是很难知道每个操作多少时间。一种算法可以执行 2N 的操作和其他 N ，但后者可能有与之相关联的大型固定时间。所以，为了这个目的，是不容易推理之间的差异 N 和 2N 。
In special, the intuition behind removing the coefficient (K*f(x) = O(f(x))) lies in what we try to measure with computational complexity. Ultimately it's all about time (or any resource, actually). But it's hard to know how much time each operation take. One algorithm may perform 2n operations and the other n, but the latter may have a large constant time associated with it. So, for this purpose, isn't easy to reason about the difference between n and 2n.
这篇关于为什么我们忽略共同efficients在大O符号？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
