找到c和n0的Big-O表示法

Question

我刚刚介绍了Big-O表示法,我已经收到了一些问题.但是我很困惑如何确定的价值n0.我必须表明它3n^3 +20n^2 + 5是O(n ^ 3).到目前为止,我有:

3n^3 + 20n^2 + 5 <= cn^3

(3 - c)n^3 + 20n^2 + 5 <= 0

5 <= n^3(c - 3) - 20n^2

5 <= n^2(n(c - 3) - 20)

我只是不知道该怎么做才能找到n0和c.有人会介意解释吗？

Answer 1

3n^3 + 20n^2 + 5 <= cn^3
=> 20n^2 + 5 <= cn^3 - 3n^3
=> 20n^2 + 5 <= n^3(c - 3)
=> 20n^2/n^3 + 5/n^3 <= n^3(c - 3)/n^3
=> 20/n + 5/n^3 <= c - 3
=> c >= 20/n + 5/n^3 + 3

根据您希望开始的条件大于条件的位置,您现在可以选择n0并找到该值.

例如,对于n0 = 1:

c >= 20/1 + 5/1 + 3 which yields c >= 28

值得注意的是,通过Big-O表示法的定义,并不要求绑定实际上是这么紧.由于这是一个简单的函数,你可以猜测并检查它(例如,为c选择100并注意条件确实是渐近的真实).

例如:

3n^3 + 20n^2 + 5 <= (5 * 10^40) * n^3 for all n >= 1

保持不变的不等式足以证明f(n)是O(n ^ 3).

为了提供更好的证明,它实际上需要显示两个常量,c并且n0存在这样的f(n) <= cg(n) for all n > n0.

使用我们的c = 28,这很容易做到:

3n^3 + 20n^2 + 5 <= 28n^3
20n^2 + 5 <= 28n^3 - 3n^3
20n^2 + 5 <= 25n^3
20/n + 5/n^3 <= 25

When n = 1: 20 + 5 <= 25 or 25 <= 25
For any n > 1, 20/n + 5/n^3 < 25, thus for all n > 1 this holds true.

Thus 3n^3 + 20n^2 + 5 <= 28n^3 is true for all n >= 1

(这是一个非常糟糕的'证明',但希望这个想法显示出来.)