big-o - 找到此功能的增长顺序的正确方法是什么？

Question

2^n + 6n^2 + 3n

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

Answer 1

2^n + n^2 + n = O(2^n)您可以通过使用无穷大的限制来证明这一点。具体来说，f(n)is O(g(n))iflim (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

请参见：

大O符号作业--代码片段算法分析？

Big O，您如何计算/近似它？

有人可以解释一下 Big-O 和 Little-O Notation 之间的区别吗？

八岁的Big-O？（没有侮辱的意思）