以大 O 表示法查找 n0

Question

这是我之前问题的延续。我学会了如何验证这种关系是否适用于

3n2 − 100n + 6 = O(n2),

因为我选择了c = 3和3n2 > 3n2 − 100n + 6；

具体如果c = 1和n0是0.06，如果n大于0.06，说n = 5，

5^2 = 25 > 3*5^2 − (100*5) + 6 = -469

现在，我似乎无法将相同的方法应用于以下等式。

3n2 − 100n + 6 = O(n3), because I choose c = 1 and n3 > 3n2 − 100n + 6 when n > 3;

令我困扰的是 "when n > 3" 部分，假设 n = 2

f(n) - 3*2^2 − (100*2) + 6 = -182

f(g) - 2^3 = 8

8 > -182

关系依旧！

我想我在某个地方犯了一个错误，因为我无法让自己确信这种关系只在 n > 3 时成立。我该怎么办？

Answer 1

正如我在中所写，满足

的常量集 (c, n0)

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

不是唯一的。此外，您不需要找到 "highest" n>n0 来显示渐近行为，而是找到任何 n0 来显示您想要证明的任何渐近关系。回想一下，因为我们对 渐近行为 感兴趣，所以我们并不真正关心函数（或算法）对于较小的 n 值（比如 n=2 或 n= 3).

此外，Big-O 描述了函数（或算法）的渐近行为的上限，但它不一定是最佳或最紧的界限。例如，

f(n) = 3n^2 - 100n + 6

    f(n) is in O(n^2) (as shown in previous thread)        (i)
    f(n) is in O(n^3) (as shown in your question here)     (ii)

在这里，我们可以同时显示 (i) 和 (ii)，但前者比后者为 f(n) 的渐近行为提供了更严格的界限。通常，我们希望找到一个尽可能紧的 Big-O 界限，但在实践中，有时一个足够好的界限就足够了。考虑以下情况：

假设我们有一些函数或算法 f(n)。此外，假设要证明这个 f(n) 是否在 O(n^2) 中需要付出巨大的努力，而证明 f(n) 在 O(n^3) 中很容易在几分钟内完成。然后说你的老板需要知道你的算法是否渐进地执行至少 "better" 而不是 n^3：因此，证明 f(n) 在 O(n^3) 中就足够了。在这种情况下，您的雇主很可能不希望您花整个下午来证明 f(n) 实际上永远 "better" 比 n^2 渐近。

应您的要求，我将添加一个解释，说明如何证明 f(n) 在 O(n^3) 中，以及为什么（非唯一）选择常量 c=3 有意义 (=很容易获得）

问题：显示f(n) = 3n2 − 100n + 6在O(n3)

我们将使用类似于中的方法。

让我们将您的函数描述为最高项与另一个函数的总和

f(n) = 3n^2 + h(n)                                       (*)
h(n) = 6 - 100n                                          (**)

在上一个线程中，我们很容易地展示了（我只是在这里列出结果）

    => h(n) < 0, given n > 6/100                         (i)
    => f(n) < 3*n^2, given n > 6/100                     (ii)

现在，考虑以下函数

g(n) = n^3                                               (***)

我们可以根据 3*n^2 以及上面的结果 (i-ii) 对这个函数说些什么？

for n = 3: g(3) = 3^3 = 3*3^2 > f(3) ((ii): since n = 3 > 6/100)
hence,    

   =>  for n > 3: g(n) > f(n)                            (iii)

现在，我们很容易达到 (iii)，因为已经有了结果 (ii)，而结果 (ii) 反过来也很容易达到。因此，选择 n0=3 是很自然的。另外，请注意 (iii) 精确地描述了关系 (+)，但具有常数 c=1；因此选择 c 作为 1.

因此，我们已经证明 (+) 对常量集 (c,n0) = (1,3) 成立，随后 f (n) 在 O(n^3).

中

同样，我们可以通过直接攻击问题 "for which smallest value of n0 does 'n^2 - 100n + 6 < n^3, n>n0' hold?" 来找到 n0 的较低值，但我们对此并不真正感兴趣：我们想看看我们研究的函数的渐近行为。

因此，任何常量集 (c,n0) 可以帮助我们显示 (+) 足够，以及任何进一步的工作寻找其他常数集（具有较小的 n0 值等）可能是代数中的一项有价值的练习，但对于我们分析 f(n) 的渐近行为没有价值。

以大 O 表示法查找 n0

Finding n0 in big O notation

big-o

asymptotic-complexity