如果f(x)= x ^ 2 + 2x + 1则如何为大O表示法找到c和k感到困惑 [英] Confused on how to find c and k for big O notation if f(x) = x^2+2x+1
问题描述
我正在从这本书中学习大O符号a>.
I am studying big O notation from this book.
大O符号的定义是:
我们说如果存在常数C和k使得| f(x)|为f(x)为O(g(x)). ≤C | g(x)|每当x> k.
We say that f (x) is O(g(x)) if there are constants C and k such that |f (x)| ≤ C|g(x)| whenever x > k.
现在是第一个示例:
示例1证明f(x)= x ^ 2 + 2x +1为O(x ^ 2).
解决方案:我们观察到，当x> 1时，因为x 1，我们可以很容易地估计f(x)的大小. 0≤x ^ 2 + 2x + 1≤x ^ 2 + 2x ^ 2 + x ^ 2 = 4x ^ 2
每当x> 1时.因此，我们可以取C = 4和k = 1作为证人，证明f(x)为O(x ^ 2).即f(x)= x ^ 2 + 2x + 1 1.(请注意，此处不必使用绝对值，因为当x为正时，这些等式中的所有函数均为正.)
EXAMPLE 1 Show that f (x) = x^2 + 2x + 1 is O(x^2).
Solution: We observe that we can readily estimate the size of f (x) when x > 1 because x 1. It follows that
0 ≤ x^2 + 2x + 1 ≤ x^2 + 2x^2 + x^2 = 4x^2
whenever x > 1. Consequently, we can take C = 4 and k = 1 as witnesses to show that f (x) is O(x^2). That is, f (x) = x^2 + 2x + 1 1. (Note that it is not necessary to use absolute values here because all functions in these equalities are positive when x is positive.)
老实说，我不知道他们是如何得到c = 4的，看起来他们像是直接跳到方程操纵上，而我的代数技能却很薄弱.但是，我找到了另一种方法[解决此问题的方法])
I honestly don't know how they got c = 4, looks like they jump straight to the equation manipulation and my algebra skills are pretty weak. However, I found another way through [The accepted answer to this question])What is an easy way for finding C and N when proving the Big-Oh of an Algorithm?) that says to add all coefficients to find c if k = 1. So x^2+2x+1 = 1+2+1 = 4.
现在k = 2，我完全迷路了:
Now for k = 2, I'm completely lost:
另外，当x> 2时，我们可以估计f(x)的大小.当x> 2时，我们有2x≤x ^ 2和1≤x ^ 2.因此，如果x> 2，我们有
0≤x ^ 2 + 2x + 1≤x ^ 2 + x ^ 2 + x ^ 2 = 3x ^ 2.
因此，C = 3和k = 2也是关系f(x)为O(x ^ 2)的见证.
Alternatively, we can estimate the size of f (x) when x > 2. When x > 2, we have 2x ≤ x^2 and 1 ≤ x^2. Consequently, if x > 2, we have
0 ≤ x^2 + 2x + 1 ≤ x^2 + x^2 + x^2 = 3x^2.
It follows that C = 3 and k = 2 are also witnesses to the relation f (x) is O(x^2).
任何人都可以解释发生了什么吗?他们使用什么方法?
Can anyone explain what is happening? What method are they using?
推荐答案
第一种选择:
C = 4?
C=4来自不等式
0 ≤ x^2 + 2x + 1 ≤ x^2 + 2x^2 + x^2 = 4x^2 = C*x^2, with C=4 (+)
(x)中的第二个不等式对于x大于1的所有x都是正确的，因为是逐项进行的
The second inequality in (+) is true for all x greater than 1, since, term by term
2x < 2x^2, given x>1
1 < x^2, given x>1
k = 1? 从上面可以看出，只要x大于1，即(p)，(+)成立.
k = 1? From above, we've shown that (+) holds as long as x is larger than 1, i.e.
(+) is true given x > k, with k=1
第二种选择:
Second alternative:
k = 2?
根据声明，我们希望研究大于2的x的f(x)，即
By the statement, we want to study f(x) for x larger than 2, i.e.
Study f(x) for x > k, k=2
给出x> 2，很明显
0 ≤ x^2 + 2x + 1 ≤ x^2 + x^2 + x^2 = 3x^2 = C*x^2, with C=3 (++)
因为，对于x> 2，我们有
since, for x>2, we have
2x = x^2 given x=2 ==> 2x < x^2 given x>2
for x=2, 1 < x^2 = 4, so 1 < x^2 for all x>2
两个示例均表明f(x)为O(x ^ 2).通过使用常量C和k，回想一下f(x)的Big-O表示法可以概括为沿线的东西
Both examples show that f(x) is O(x^2). By using your constants C and k, recall that then Big-O notation for f(x) can be summarized as something along the lines
...如果我们可以找到一个常数C，我们可以说f(x)是O(g(x)) | f(x)|小于C | g(x)|或所有大于k的x，即对于所有 x> k. (*)
... we can say that f(x) is O(g(x)) if we can find a constant C such that |f(x)| is less than C|g(x)| or all x larger than k, i.e., for all x>k. (*)
这绝不意味着我们需要找到(C，k)的唯一集合来证明某些f(x)是某个O(g(x))，而只是某个集合(C，k)这样上面的(*)成立.
This, by no means, implies that we need to find a unique set of (C, k) to prove that some f(x) is some O(g(x)), just some set (C, k) such that (*) above holds.
例如参见下面的链接提供了一些有关如何指定函数渐近行为的参考: https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-o-notation
See e.g. the following link for some reference on how to specify the asymptotic behaviour of a function: https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-o-notation
这篇关于如果f(x)= x ^ 2 + 2x + 1则如何为大O表示法找到c和k感到困惑的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
