对于大O符号，2 ^ n或n ^ 2中占优势的术语是什么
我一直在看大O符号，并且遇到了2^n+n^2的操作计数。 我明白大O符号的做法是去除常量和低位项，但我无法弄清楚哪一个要做O(n) 。 我认为这可能是2^n但没有运气发现任何建议。
随着时间的推移看看增长因素。 对于n的前8个值， O(n^2)出：
0，1，4，9，16，25，36，49 ...
O(2^n)产生两个幂：
1，2，4，8，16，32，64，128 ...
它应该是相当明显的哪一个增长更快。
请注意，一般规则即使在不同的基数和指数下也适用。 对于较小的n ， O(1.1^n)初始值可能比O(n^10)的初值要低，但当指数n接近无穷大时，指数大于1的所有指数增长最终都会超出固定的指数多项式增长。
按照L'Hopital的规定：
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)之后n增长过去的一些常数和。一种思考f(n) = o(g(n))是当n增长到无穷大时， g(n)将会更快地超过f(n) 。换句话说：
当且仅当极限f(n)/g(n)随着n变为无穷大而变为零时， f(n) = o(g(n)) 。
o(g(n)是f(n) = O(g(n))的严格更强的条件。
或者，您只需直接使用该定义：找到一些a和b ，以使n^2 <= a | 2^n | n^2 <= a | 2^n | 对于所有n >= b ，这是简单的代数运算。
2 ^ n是占优势的，因为对于较大的n，它增长得更快。
链接地址: http://www.djcxy.com/p/40043.html上一篇: Whats the dominant term in 2^n or n^2 for big O notation