我一直在查看Big O表示法，并且遇到了可操作的问题2^n+n^2。我知道大O表示法的做法是删除常数和低阶项，但是我不知道该作哪个O(n)。我认为可能是，2^n但是没有运气找到任何暗示这一点的机会。
查看随时间的增长因素。对于 的前八个值n，计算O(n^2)为：
0, 1, 4, 9, 16, 25, 36, 49...
O(2^n) 产生两个幂：
1, 2, 4, 8, 16, 32, 64, 128...
哪个增长更快应该是相当明显的。
请注意，即使底数和指数不同，一般规则也适用。O(1.1^n)最初的工作量可能低于O(n^10)small n，但所有指数大于 1 的指数增长最终都会超过固定指数多项式增长，因为它n接近无穷大。
根据洛必达法则：
lim_{n -> infinity} (n^2 / 2^n )
= 1/log(2) lim_{n -> infinity} (2n / 2^n)
= 1/log(2)^2 lim_{n -> infinity} (2 / 2^n)
= 0
我们有n^2 = o(2^n)这意味着n^2 = O(2^n).
如果这个证明没有意义：根据定义，f(n) = O(g(n)当且仅当在增长超过某个常数后f(n)限制在某个常数倍内。一种思考方式是，随着增长到无穷大，它将继续增长得更快。换句话说：g(n)nf(n) = o(g(n))ng(n)f(n)
f(n) = o(g(n))当且仅当极限随着趋向f(n)/g(n)无穷大而变为零n。
o(g(n)是一个严格更强的条件f(n) = O(g(n))。
或者，您只需要直接使用定义：Find somea和bsuch that n^2 <= a | 2^n |for all n >= b，这是简单的代数运算。