简化大O符号

Question

我为我可怜的数学技能提前道歉...

我想了解Big O Notation背后的数学如何工作。我从this了解到，2n^2 = O(n^3)已经证明n = O(n^2)，但我似乎也证明n^3 = O(n^2)这是没有意义的，我敢肯定是错误的。以下是我如何“证明”这一点：

n^3 = O(n^2) 
n^3 <= c*n^2 
n <= c  #n^2 cancels out 
1 <= c/n 
c = 1; n0 = 1 

我在做什么错？

Answer 1

1 <= c/n并不适用于所有n > n0，例如，对于n = 2（与N0 = 1，C = 1），你会得到：

1 <= 1/2 

，这是一个伪命题。

在大O表示法的关键是，你需要证明，对于所有n > n0，方程f(n) <= C*g(n)持有（对于某些C,n0），以显示f(n)是O(g(n))

Answer 2

通常大O符号被定义为具有共同渐近行为的一组函数。也就是说，随着n的增长，功能将如何增长。

在这种情况下，我们清楚地看到n^3超过n^2，所以它们实际上在不同的O类中。