对大O表示法感到困惑 [英] Confused on big O notation
问题描述
根据这本书，大O意思是:
f(n)= O(g(n))表示c·g(n)是f(n)的上限.因此，存在一个常数c，使得对于足够大的n(即，对于某个常数n0，n≥n0)，f(n)始终≤c·g(n).
f(n) = O(g(n)) means c · g(n) is an upper bound on f(n). Thus there exists some constant c such that f(n) is always ≤ c · g(n), for large enough n (i.e. , n ≥ n0 for some constant n0).
我很难理解下面的大O方程
I have trubble understanding the following big O equation
3n2-100n + 6 = O(n2)，因为我选择c = 3且3n2> 3n2-100n + 6;
3n2 − 100n + 6 = O(n2), because I choose c = 3 and 3n2 > 3n2 − 100n + 6;
3如何成为一个因素?在3n2 − 100n + 6中，如果我们丢弃低阶项-100n和6，那么3n2和3.n2是否相同?该方程如何求解?
How can 3 be a factor? In 3n2 − 100n + 6, if we drop the low order terms -100n and 6, aren't 3n2 and 3.n2 the same? How to solve this equation?
推荐答案
让我们看看您为f(n) in O(g(n))发布的定义:
Let's look at the definition you posted for f(n) in O(g(n)):
f(n)= O(g(n))意味着c·g(n)是f(n)的上限.因此那里 存在一些常数c ，使得f(n)始终≤c·g(n)，对于 足够大的n (即对于某个常数n0，n≥n0).
f(n) = O(g(n)) means c · g(n) is an upper bound on f(n). Thus there exists some constant c such that f(n) is always ≤ c · g(n), for large enough n (i.e. , n ≥ n0 for some constant n0).
因此，我们只需要找到一组可以满足的常量(c，n0)
So, we only need to find one set of constants (c, n0) that fulfils
f(n) < c · g(n), for all n > n0, (+)
但此设置不是唯一.也就是说，找到常数(c，n0)使得(+)成立的问题是简并.实际上，如果存在任何这样的常量对，将存在无限数量的不同这样的常量对.
but this set is not unique. I.e., the problem of finding the constants (c, n0) such that (+) holds is degenerate. In fact, if any such pair of constants exists, there will exist an infinite amount of different such pairs.
请注意，这里我切换到严格的不等式，这实际上只是一个口味问题，但是我更喜欢后者.现在，我们可以用可能更易于理解的术语重新声明Big-O定义:
Note that here I've switched to strict inequalities, which is really only a matter of taste, but I prefer this latter convention. Now, we can re-state the Big-O definition in possibly more easy-to-understand terms:
...如果我们可以找到一个常数c，我们可以说f(n)是O(g(n)). f(n)小于c·g(n)或所有n都大于n0，即对于所有 n> n0.
... we can say that f(n) is O(g(n)) if we can find a constant c such that f(n) is less than c·g(n) or all n larger than n0, i.e., for all n>n0.
现在，让我们看一下函数f(n)
Now, let's look at your function f(n)
f(n) = 3n^2 - 100n + 6 (*)
让我们将您的功能描述为最高期限和其他功能的总和
Let's describe your functions as a sum of it's highest term and another functions
f(n) = 3n^2 + h(n) (**)
h(n) = 6 - 100n (***)
我们现在分别研究h(n)和f(n)的行为:
We now study the behaviour of h(n) and f(n), respectively:
h(n) = 6 - 100n
what can we say about this expression?
=> if n > 6/100, then h(n) < 0, since 6 - 100*(6/100) = 0
=> h(n) < 0, given n > 6/100 (i)
f(n) = 3n^2 + h(n)
what can we say about this expression, given (i)?
=> if n > 6/100, the f(n) = 3n^2 + h(n) < 3n^2
=> f(n) < c*n^2, with c=3, given n > 6/100 (ii)
好！
- 从(ii)中，我们可以选择常数 c = 3 ，假设我们选择的另一个常数n0大于6/100.让我们选择满足此条件的第一个整数: n0 = 1 .
- From (ii) we can choose constant c=3, given that we choose the other constant n0 as larger than 6/100. Lets choose the first integer that fulfils this: n0=1.
因此，我们证明了(+)常数集**(c，n0)=(3,1)的金，随后， f(n)在O(n ^ 2).
Hence, we've shown that (+) golds for constant set **(c,n0) = (3,1), and subsequently, f(n) is in O(n^2).
有关渐近行为的参考，请参见例如
For a reference on asymptotic behaviour, see e.g.
这篇关于对大O表示法感到困惑的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
