找到这个函数的增长顺序的正确方法是什么？

Question

2^n + 6n^2 + 3n

我想这只是O（2^n），使用最高阶的术语，但什么是正式的方法来证明这一点呢？

Answer 1

你能证明2^n + n^2 + n = O(2^n)通过无限使用限制。具体而言，如果lim (n->inf.) f(n)/g(n)是有限的，则f(n)是O(g(n))。

lim (n->inf.) ((2^n + n^2 + n)/2^n) 

既然你有INF/INF，一个indeterminate form，您可以使用L'Hopital's rule和分化的分子和分母，直到你得到的东西，你可以工作：

lim (n->inf.) ((ln(2)*2^n + 2n + 1)/(ln(2)*2^n)) 
lim (n->inf.) ((ln(2)*ln(2)*2^n + 2)/(ln(2)*ln(2)*2^n)) 
lim (n->inf.) ((ln(2)*ln(2)*ln(2)*2^n)/(ln(2)*ln(2)*ln(2)*2^n)) 

限制为1，所以2^n + n^2 + n确实是O(2^n)。

Answer 2

请参阅：

Big O Notation Homework--Code Fragment Algorithm Analysis?

Big O, how do you calculate/approximate it?

Can someone please explain the difference between Big-O and Little-O Notation?

Big-O for Eight Year Olds?（并不意味着是侮辱）