找到這個函數的增長順序的正確方法是什麼？

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?（並不意味着是侮辱）