big-o - この関数の成長の順序を見つけるための適切な方法は何ですか？

Question

2 ^ n + 6n ^ 2 + 3n

最高位の項を使用したO（2 ^ n）だと思いますが、これを証明するための正式なアプローチは何ですか？

Answer 1

2^n + n^2 + n = O(2^n)無限区間の極限を使用することで、それを証明できます。具体的にf(n)は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

参照してください：

Big O記法の宿題-コードフラグメントアルゴリズム分析？

Big O、どのように計算/概算しますか？

Big-O表記とLittle-O表記の違いを誰かに説明してもらえますか？

8歳のBig-O？（侮辱することを意図したものではありません）