21672

大O符号的发现c和N0(Big-O notation finding c and n0)

我刚刚被介绍到大O符号,我一直在考虑一些Question。 不过,我很困惑,如何确定的值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

值得一提的是由大O符号的定义,它不是必需的约束实际上是这种紧密。 由于这是一个简单的功能,你可以只是猜测和检查(例如,挑选100 c和注意,条件确实是真的渐近)。

例如:

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

不平等持真,就足以证明,F(N)为O(n ^ 3)。


为了提供更好的证明,它实际上需要被显示的两个常数, cn0存在,使得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

(这是一个相当严重的做“证据”,但希望这个想法表示。)



Answer 2:

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

Answer 3:

如果您有f(n) = (3n^3 + 20n^2 + 5)你想看看它的O(g(n))其中g(n) = n^3 ,我相信你可以采取的限制的f(n)/g(n)为n->无穷大。

因为限制是3,你可以看到, 3n^3 + 20n^2 + 5只作为快速成长,如n^3 。 当你有一个像多项式3n^3 + 20n^2 + 5 ,您可以通过检查的最大的订单项永远是价值告诉O(f(n))

这不是一个很大的帮助找到N 0和C,但它是一个相对简单的方法来判断事物的顺序是什么。 正如其他人在这里说,你可以随便挑N 0,然后计算C.

如果选择N 0 = 1,那么你有3*(1^3) + 20*1^2 + 5 = 28 。 因此,如果c1^3 <= 28 ,c必须是28.你已经示出存在有交N0满足该条件,所以你已经证明F(N)是O(n ^ 3)



Answer 4:

除n ^ 3,我们得到3 + 20 / N + 5 / N ^ 3 <= C 20 / N + 5 / N ^ 3 <= C-3

取C值作为10 20 / N + 5 / N ^ 3 <= 7

我们需要直到条件得到满足C = 10和N0 = 3会给出解决方案来解决这个对于不同的n值



文章来源: Big-O notation finding c and n0

Recommend