big-o - 大 O 表示法中低阶项的作用

Question

在大O表示法中，我们总是说在大多数情况下我们应该忽略常数因子。也就是说，而不是写作，

3n^2-100n+6

我们几乎总是满意

n^2

因为该项是等式中增长最快的项。

但是我发现很多算法类(class)开始比较函数与许多术语

2n^2+120n+5 = n^2 的大 O

然后为这些长函数找到 c 和 n0，然后建议最终忽略低阶项。

我的问题是，通过尝试理解和分析这些带有许多术语的函数，我会得到什么？在这个月之前，我已经能够轻松理解 O(1)、O(n)、O(LOG(n))、O(N^3) 的含义。但是，如果我只依赖这个常用的函数，我是否会错过一些重要的概念？如果我跳过分析这些长函数，我会错过什么？

Answer 1

首先让我们描述一下 f(n) is in O(g(n)) 的含义。 :

... 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.

在方程中:我们需要找到一组满足条件的常量(c, n0)

f(n) < c · g(n), for all n > n0,                        (+)

现在，结果是f(n) is in O(g(n))有时以不同的形式呈现，例如如f(n) = O(g(n))或f(n) ∈ O(g(n)) ，但声明是一样的。因此，从你的问题来看，声明 2n^2+120n+5 = big O of n^2只是:

f(n) = 2n^2 + 120n + 5

a result after some analysis: f(n) is in O(g(n)), where

    g(n) = n^2

好吧，抛开这个问题，我们看看我们想要渐近分析的函数中的常数项，然后让我们从教育角度来看它，但是使用您的示例。

---

由于任何大 O 分析的结果都是函数的渐近行为，因此除了一些非常不寻常的情况外，常数项对此行为没有任何影响。然而，常数因子会影响如何选择常数对 (c, n0)，用于表明对于某些函数 f(n) 和 g(n)，f(n) 的复杂度为 O(g(n))，即，非唯一常数对 (c, n0) 用于表明 (+) 成立。我们可以说常数项不会影响我们的分析结果，但它会影响我们对此结果的推导。

让我们看看您的函数以及另一个相关函数

f(n) = 2n^2 + 120n + 5                                        (x)
h(n) = 2n^2 + 120n + 22500                                    (xx)

使用与 this thread 类似的方法，对于f(n) ，我们可以显示:

linear term: 

    120n < n^2 for n > 120 (verify: 120n = n^2 at n = 120)    (i)

constant term:

    5 < n^2 for e.g. n > 3 (verify: 3^2 = 9 > 5)              (ii)

这意味着如果我们替换 120n以及 5在 (x) 中 n^2我们可以得出以下不等式结果:

Given that n > 120, we have:
2n^2 + n^2 + n^2 = 4n^2 > {by (ii)} > 2n^2 + 120n + 5 = f(n)  (iii)

从(iii)中，我们可以选择(c, n0) = (4, 120) ，并且 (iii) 然后表明这些常数满足 (+) f(n)与 g(n) = n^2 ，因此

result: f(n) is in O(n^2)

现在，对于 h(n) ，我们类似地有:

linear term (same as for f(n)) 

    120n < n^2 for n > 120 (verify: 120n = n^2 at n = 120)    (I)

constant term:

    22500 < n^2 for e.g. n > 150 (verify: 150^2 = 22500)      (II)

在本例中，我们替换 120n以及 22500在 (xx) n^2 ，但我们需要对 n 进行更大的小于约束才能使它们成立，即 n > 150 。因此，我们有以下观点:

Given that n > 150, we have:
2n^2 + n^2 + n^2 = 4n^2 > {by (ii)} > 2n^2 + 120n + 5 = h(n)  (III)

与 f(n) 相同，我们可以在这里选择(c, n0) = (4, 150) ，并且 (III) 然后表明这些常数满足 (+) h(n) ，与 g(n) = n^2 ，因此

result: h(n) is in O(n^2)

因此，函数 f(n) 和 h(n) 的结果相同，但我们必须使用不同的常数 (c,n0) 来显示这些结果(即，推导有些不同)。最后请注意:

• 自然地，常数 (c,n0) = (4,150)(用于 h(n) 分析)也有效地表明 f(n) 在 O(n^2) 中，即 (+) 成立对于 f(n) 且 g(n)=n^2。
• 但是，反之亦然:(c,n0) = (4,120) 不能用于证明 (+) 对于 h(n) 成立(其中 g(n)=n^2)。

本次讨论的核心是:

1. 只要您查看足够大的 n 值，您将能够将关系中的常数项描述为 constant < dominantTerm(n) ，在我们的示例中，我们查看与主导项 n^2 的关系。
2. 函数的渐近行为(除了一些非常不寻常的情况外)不会依赖于常数项，因此我们最好完全跳过它们。然而，为了对某些函数的渐近行为进行严格证明，我们还需要考虑常数项。