需要O(n^2)个计算辅助

Question

我就是想不出这个: 5n2 + 3n +9= O(n2)。选择c和n0。证明使用f(n) <= c.g(n)。

我试着把它压缩成3n +9/c-5 <= n^2，但我仍然找不到解决方案。我想我只是从错误的方式来处理它。

Stackoverflow，请帮帮我！:)

Answer 1

我真的不理解这个问题，但如果你只想证明"5n^2 + 3n +9= O(n^2)"，你必须证明"(5n^2 + 3n + 9)/n^2 -> k in R when n -> +inf“。这很容易证明："(5n^2 + 3n + 9)/n^2 =5+ 3/n + 9/n^2 -> 5+0+ 0“

Answer 2

以c=11和n0=2为例，我们想证明对于所有n>= n0，f(n) = 5n^2 + 3n +9< 11*g(n) = 11n^2。等价地，对于所有n个>= n0，显示6n^2 - 3n -9 >= 0。该表达式因数为(6n-9)(n+1) >= 0。这只在(-1，1.5)上是负的，所以对于所有n>2，我们有f(n) < c*g(n)。