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

Question

2 ^ n + 6n ^ 2 + 3n

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

Answer 1

您可以通过在无穷远处使用限制来证明 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，不确定表格，你可以使用 L'Hopital的规则并区分分子和分母直到你得到某些东西你可以使用：

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表示法作业 - 代码片段算法分析？

大O，您如何计算/近似？

可以有人请解释Big-O和Little-O表示法之间的区别吗？

八岁以上的Big-O？（不应该是侮辱性）