大O表示法找到c和n0 [英] Big-O notation finding c and n0

问题描述

我刚刚被介绍了Big-O表示法，并且给了我一些问题.但是，我对如何确定n0的值感到困惑. 我必须证明3n^3 +20n^2 + 5是O(n ^ 3).到目前为止，我有:

I've just been introduced to Big-O notation and I've been given some questions. However I'm confused as to how to determine the value of n0. I have to show that 3n^3 +20n^2 + 5 is O(n^3). So far I have:

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.有人介意解释吗?

I just don't know what to do from here to find n0 and c. Would someone mind explaining?

推荐答案

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并找到该值.

Depending on where you want the greater than condition to begin, you can now choose n0 and find the value.

例如，对于n0 = 1:

For example, for n0 = 1:

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

值得注意的是，按照Big-O表示法的定义，实际上并不需要严格限制范围.由于这是一个简单的函数，因此您可以猜测并检查它(例如，为c选择100，请注意，该条件确实在渐近条件下成立).

It's worth noting that by the definition of Big-O notation, it's not required that the bound actually be this tight. Since this is a simple function, you could just guess-and-check it (for example, pick 100 for c and note that the condition is indeed true asymptotically).

例如:

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

不等式为true足以证明f(n)为O(n ^ 3).

That inequality holding true is enough to prove that f(n) is O(n^3).

为了提供更好的证明，实际上需要证明存在两个常量c和n0使得f(n) <= cg(n) for all n > n0.

To offer a better proof, it actually needs to be shown that two constants, c and n0 exist such that f(n) <= cg(n) for all n > n0.

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

Using our c = 28, this is very easy to do:

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

(这是做得不好的证明"，但希望这个想法能显示出来.)

(That's a pretty badly done 'proof' but hopefully the idea shows.)

这篇关于大O表示法找到c和n0的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！