如果 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
我正在学习 this book 的大 O 表示法。
大O符号的定义是：
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.
现在是第一个例子：
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 的，看起来他们直接跳到方程式操作，我的代数技能很弱。但是，我通过 [The accepted answer to this question])What is an easy way for finding C and N when proving the Big-Oh of an Algorithm?) 找到了另一种方法，它说如果 k = 1，则添加所有系数以找到 c。所以 x^2+2x+1 = 1+2+1 = 4.
现在 k = 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).
谁能解释一下发生了什么？他们使用什么方法？
第一个选择：
C=4?
C=4来自不等式
0 ≤ x^2 + 2x + 1 ≤ x^2 + 2x^2 + x^2 = 4x^2 = C*x^2, with C=4 (+)
(+) 中的第二个不等式对所有大于 1 的 x 都成立，因为，逐项
2x < 2x^2, given x>1
1 < x^2, given x>1
k = 1?
从上面可以看出，只要 x 大于 1，(+) 就成立，即
(+) is true given x > k, with k=1
第二个选择：
k=2?
根据声明，我们要研究x大于2的f(x)，即
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，我们有
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 符号可以概括为
... 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) k) 使得上面的 (*) 成立。
参见例如以下 link 提供了一些关于如何指定函数的渐近行为的参考：
https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-o-notation
我正在学习 this book 的大 O 表示法。
大O符号的定义是：
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.
现在是第一个例子：
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 的，看起来他们直接跳到方程式操作，我的代数技能很弱。但是，我通过 [The accepted answer to this question])What is an easy way for finding C and N when proving the Big-Oh of an Algorithm?) 找到了另一种方法，它说如果 k = 1，则添加所有系数以找到 c。所以 x^2+2x+1 = 1+2+1 = 4.
现在 k = 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).
谁能解释一下发生了什么？他们使用什么方法？
第一个选择：
C=4?
C=4来自不等式
0 ≤ x^2 + 2x + 1 ≤ x^2 + 2x^2 + x^2 = 4x^2 = C*x^2, with C=4 (+)
(+) 中的第二个不等式对所有大于 1 的 x 都成立，因为，逐项
2x < 2x^2, given x>1
1 < x^2, given x>1
k = 1? 从上面可以看出，只要 x 大于 1，(+) 就成立，即
(+) is true given x > k, with k=1
第二个选择：
k=2?
根据声明，我们要研究x大于2的f(x)，即
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，我们有
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 符号可以概括为
... 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) k) 使得上面的 (*) 成立。
参见例如以下 link 提供了一些关于如何指定函数的渐近行为的参考： https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-o-notation