如果 f(x) = x^2+2x+1 则对如何找到大 O 表示法的 c 和 k 感到困惑

Question

我正在学习这本书中的大O表示法。

\n\n

大O表示法的定义是：

\n\n

\n如果存在常数 C 和 k 使得 |f (x)| ，我们说 f (x) 是 O(g(x)) \xe2\x89\xa4 C|g(x)| 每当 x > k 时。\n

\n\n

现在这是第一个例子：

\n\n

\n示例 1 证明 f (x) = x^2 + 2x + 1 是 O(x^2)。
\n解：我们观察到，当 x > 1 时，我们可以很容易地估计 f (x) 的大小，因为 x 1。因此
\n0 \xe2\x89\xa4 x^2 + 2x + 1 \xe2\x89\xa4 x ^2 + 2x^2 + x^2 = 4x^2
\n只要 x > 1。因此，我们可以以 C = 4 和 k = 1 为证，证明 f (x) 是 O(x^2)。即f(x)=x^2+2x+1\n1。（请注意，此处不必使用绝对值，因为当 x 为正数时，这些等式中的所有函数均为正数。） \n

\n\n

老实说，我不知道他们是如何得到 c = 4 的，看起来他们直接跳到方程运算，而我的代数技能相当薄弱。然而，我通过[这个问题的公认答案]找到了另一种方法）在证明算法的 Big-Oh 时找到 C 和 N 的简单方法是什么？）表示如果 k = 1，则将所有系数相加来找到 c。因此 x^2+2x+1 = 1+2+1 = 4。

\n\n

现在对于 k = 2，我完全迷失了：

\n\n

\n或者，当 x > 2 时，我们可以估计 f (x) 的大小。当 x > 2 时，我们有 2x \xe2\x89\xa4 x^2 和 1 \xe2\x89\xa4 x^2。因此，如果 x > 2，则有
\n0 \xe2\x89\xa4 x^2 + 2x + 1 \xe2\x89\xa4 x^2 + x^2 + x^2 = 3x^2。
\n因此，C = 3 和 k = 2 也证明关系 f (x) 是 O(x^2)。\n

\n\n

谁能解释发生了什么？他们使用什么方法？

\n

Answer 1

第一种选择：

\n\n

C=4？

\n\n

来自C=4不平等

\n\n

0 \xe2\x89\xa4 x^2 + 2x + 1 \xe2\x89\xa4 x^2 + 2x^2 + x^2 = 4x^2 = C*x^2, with C=4   (+)\n

\n\n

(+) 中的第二个不等式对于所有大于 1 的 x 都成立，因为逐项

\n\n

2x < 2x^2, given x>1\n1 < x^2, given x>1\n

\n\n

k = 1? \n从上面我们已经证明，只要 x 大于 1，(+) 就成立，即

\n\n

(+) is true given x > k, with k=1\n

\n\n\n\n

第二种选择：

\n\n

k=2？

\n\n

根据陈述，我们要研究 x 大于 2 时的 f(x)，即

\n\n

Study f(x) for x > k, k=2\n

\n\n

给定 x > 2，显然

\n\n

0 \xe2\x89\xa4 x^2 + 2x + 1 \xe2\x89\xa4 x^2 + x^2 + x^2 = 3x^2 = C*x^2, with C=3 (++)\n

\n\n

因为，对于 x>2，我们有

\n\n

2x = x^2 given x=2 ==> 2x < x^2 given x>2\nfor x=2, 1 < x^2 = 4, so 1 < x^2 for all x>2\n

\n\n\n\n

这两个例子都表明 f(x) 是 O(x^2)。通过使用常数 C 和 k，请记住 f(x) 的 Big-O 表示法可以概括为以下内容

\n\n

\n

...我们可以说 f(x) 是 O(g(x)) 如果我们可以找到一个常数 C 使得 |f(x)| 小于 C|g(x)| 或所有 x 都大于 k，即，对于所有\n x>k。(*)

\n

\n\n

这绝不意味着我们需要找到一组唯一的 (C, k) 来证明某个 f(x) 是某个 O(g(x))，只是某个集合 (C, k) 使得 ( *) 以上成立。

\n\n

有关如何指定函数渐近行为的一些参考，请参阅以下链接：\n https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-o-notation

\n