刚刚向我介绍了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。有人介意解释吗？
最佳答案
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
（这是一个做得不好的“证明”，但希望这个想法能显示出来。）
关于big-o - 大O表示法找到c和n0，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14249151/