对大O表示法感到困惑

编程入门行业动态更新时间:2024-10-23 14:23:45

本文介绍了对大O表示法感到困惑的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！问题描述

根据这本书，大O意思是:

f(n)= O(g(n))表示c·g(n)是f(n)的上限.因此，存在一个常数c，使得对于足够大的n(即，对于某个常数n0，n≥n0)，f(n)始终≤c·g(n). f(n) = O(g(n)) means c · g(n) is an upper bound on f(n). Thus there exists some constant c such that f(n) is always ≤ c · g(n), for large enough n (i.e. , n ≥ n0 for some constant n0).

我很难理解下面的大O方程

I have trubble understanding the following big O equation

3n2-100n + 6 = O(n2)，因为我选择c = 3且3n2> 3n2-100n + 6;

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

3如何成为一个因素?在3n2 − 100n + 6中，如果我们丢弃低阶项-100n和6，那么3n2和3.n2是否相同?该方程如何求解?

How can 3 be a factor? In 3n2 − 100n + 6, if we drop the low order terms -100n and 6, aren't 3n2 and 3.n2 the same? How to solve this equation?

推荐答案

让我们看看您为f(n) in O(g(n))发布的定义:

Let's look at the definition you posted for f(n) in O(g(n)):

f(n)= O(g(n))意味着c·g(n)是f(n)的上限.因此那里存在一些常数c ，使得f(n)始终≤c·g(n)，对于足够大的n (即对于某个常数n0，n≥n0).

f(n) = O(g(n)) means c · g(n) is an upper bound on f(n). Thus there exists some constant c such that f(n) is always ≤ c · g(n), for large enough n (i.e. , n ≥ n0 for some constant n0).

因此，我们只需要找到一组可以满足的常量(c，n0)

So, we only need to find one set of constants (c, n0) that fulfils

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

但此设置不是唯一.也就是说，找到常数(c，n0)使得(+)成立的问题是简并.实际上，如果存在任何这样的常量对，将存在无限数量的不同这样的常量对.

but this set is not unique. I.e., the problem of finding the constants (c, n0) such that (+) holds is degenerate. In fact, if any such pair of constants exists, there will exist an infinite amount of different such pairs.

请注意，这里我切换到严格的不等式，这实际上只是一个口味问题，但是我更喜欢后者.现在，我们可以用可能更易于理解的术语重新声明Big-O定义:

Note that here I've switched to strict inequalities, which is really only a matter of taste, but I prefer this latter convention. Now, we can re-state the Big-O definition in possibly more easy-to-understand terms:

...如果我们可以找到一个常数c，我们可以说f(n)是O(g(n)). f(n)小于c·g(n)或所有n都大于n0，即对于所有 n> n0.

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

现在，让我们看一下函数f(n)

Now, let's look at your function f(n)

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

让我们将您的功能描述为最高期限和其他功能的总和

Let's describe your functions as a sum of it's highest term and another functions

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

我们现在分别研究h(n)和f(n)的行为:

We now study the behaviour of h(n) and f(n), respectively:

h(n) = 6 - 100n what can we say about this expression? => if n > 6/100, then h(n) < 0, since 6 - 100*(6/100) = 0 => h(n) < 0, given n > 6/100 (i) f(n) = 3n^2 + h(n) what can we say about this expression, given (i)? => if n > 6/100, the f(n) = 3n^2 + h(n) < 3n^2 => f(n) < c*n^2, with c=3, given n > 6/100 (ii)

好！

从(ii)中，我们可以选择常数 c = 3 ，假设我们选择的另一个常数n0大于6/100.让我们选择满足此条件的第一个整数: n0 = 1 .

From (ii) we can choose constant c=3, given that we choose the other constant n0 as larger than 6/100. Lets choose the first integer that fulfils this: n0=1.

因此，我们证明了(+)常数集**(c，n0)=(3,1)的金，随后， f(n)在O(n ^ 2).

Hence, we've shown that (+) golds for constant set **(c,n0) = (3,1), and subsequently, f(n) is in O(n^2).

有关渐近行为的参考，请参见例如

For a reference on asymptotic behaviour, see e.g.