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

你可以证明 2^n + n^2 + n = O(2^n) 在无穷远处使用极限。明确地, f(n) 是 O(g(n)) 如果 lim (n->inf.) f(n)/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) .

请参阅:

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? (不是有意侮辱)