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

Question

2 ^ n + 6n ^ 2 + 3n

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

Answer 1

無限で制限を使用することで、 2 ^ n + n ^ 2 + n = O（2 ^ n）であることを証明できます。具体的には、 lim（n-＆gt; inf。）f（n）/ g（n）の場合、 f（n）は O（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表記法の宿題-コードフラグメントアルゴリズム分析？

ビッグO、どのように計算/概算しますか

誰かがBig-OとLittle-O表記の違いを説明してください。

8歳のBig-O？（という意味ではありませんs辱）