练习：证明 5n^2 + 2n - 1 对于 n >= 1是 O(n ^ 2)
这就是我所做的：
- 5n^2 + 2n - 1 < 5n^2 + 2n。
- 5nˆ2 - 1 < 5nˆ2
这意味着 C= 5 和 n0 = 1
我有点紧张，因为我觉得这太简单了。我做错了什么还是没关系？
谢谢！
首先，大O符号是关于渐近增长的，所以n >= 1实际上是多余的。
根据大 O 的定义，f(n) = O(g(n))如果存在某个c, n0 > 0stn > n0则它持有那个f(n) <= cg(n)。
所以在我们的例子中：5n^2 + 2n - 1 <= 5n^2 + 2n <= 5n^2 + 2n^2 = 7n^2对于每个自然整数，它都持有n^2 >= n。
选择c = 7, n0 = 1和n > n0我们得到的一切5n^2 + 2n -1 <= 7n^2 = cn^2。
结论：5n^2 + 2n - 1 = O(n^2)。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句