f(x) = 4x^2 - 5x + 3 是如何导出的 O(x^2)

How is f(x) = 4x^2 - 5x + 3 is O(x^2) derived

下面是用来证明上述的步骤

|f(x)| = |4x^2 – 5x + 3|
<= |4x^2|+ |- 5x| + |3|
<= 4x^2 + 5x + 3, for all x > 0
<= 4x^2 + 5x^2 + 3x^2, for all x > 1
<= 12x^2, for all x > 1

因此我们得出结论 f(x) 是 O(x^2)

我referred this但是没用

谁能一步步解释上面的证明？

  1. 为什么取f(x)的绝对值？
  2. 为什么以及如何将所有术语替换为 x^2 术语？

准备工作

我们首先粗略地说明函数或算法的定义 f 在 O(g(n)):

If a function f is in O(g(n)), then c · g(n) is an upper bound on f(n), for some non-negative constant c such that f(n) ≤ c · g(n) holds, for sufficiently large n (i.e. , n ≥ n0 for some constant n0).

因此，为了证明f ∈ O(g(n))，我们需要找到一组满足

的（非负）常数(c, n0) 
f(n) ≤ c · g(n), for all n ≥ n0,                                (+)

但是，我们注意到这个集合 不是唯一的 ；找到使 (+) 成立的常数 (c, n0) 的问题是 退化 。事实上，如果存在任何这样的常数对，就会存在无数个不同的这样的常数对。

分析

根据惯例，我们将使用变量名称 n 而不是 x.

来分析您的示例 
f(n) = 4n^2 - 5n + 3                                            (++)

现在，对于您的示例，我们可以假设，在不失一般性的情况下（因为我们正在研究渐近复杂性："large" n 的 function/algorithm 行为）n > n0 其中 n0 > 0。这将对应于您在分析 x 的绝对值的问题中显示的分析。无论如何，鉴于此假设，以下内容成立：

f(n) = 4n^2 - 5n + 3 < 4n^2 + 3, for all n > n0

现在让，同样不失一般性，n0等于2（我们可以选择任何值，但让我们选择2这里）。对于 n0 = 2，自然 n^2 > 3 对 n > n0 成立，这意味着以下内容成立：

f(n) = 4n^2 - 5n + 3 < 4n^2 + 3 < 4n^2 + n^2, for all n > n0 = 2
f(n) < 5n^2, for all n > n0 = 2

现在选择c = 5然后让g(n) = n^2:

f(n) < c · g(n), for all n > n0,
                 with c = 5, n0 = 2, g(n) = n^2

因此，根据 (+)，我们已经证明 (++) 中定义的 f 在 O(g(n)) = O(n^2).

中