algorithm - 为什么线性函数的复杂度与二次方程的复杂度相同

Question

我正在学习算法。所以，我带来了一些非常有趣的东西。

(a*n)+b线性方程 ( )的渐近界是O(n^2).. 对于所有a>0.

这与不那么令人惊讶的相同..a* n^2 + b* n + c

为什么？

Answer 1

因为big-oh给了你一个上限。你的第一个功能也是O(n^3), O(n^4), O(n^2012)等等。

big-oh 的定义基本上是说，f(n) is O(g(n))如果存在一些k这样的东西，那么n > k我们有g(n) > f(n)。

研究big -theta以获得更强/更紧密的界限。