n^2の大きなOについて混乱している^ 2 n

Question

私は、次の式O(2^n + n^100)が重要でない部分を削除すると、O(2^n)になることを本で読んだ。 nの値が3である場合、私の理解によると、部分n^100はより多くの実行回数を有すると思われるので、私は混乱しています。私は何が欠けていますか？

Answer 1

Big O表記は性質上漸近的であり、これはnが無限大の傾向にあると考えることを意味します。あなたは右のそれのためのn = 3、n^100ある

は、私たちがnはるかに大きいために

1000以上のため O(2^n + n^100)で n^100を無視することができます 2^nは常に n^100よりも大きい場合、 2^nより大きいが、一度、N> 1000ランダウの記号の正式な数学的記述Wikipediaの記事は、この答えはまた良い仕事をしていません以下の数学的な説明については良い仕事を

行います

What is a plain English explanation of "Big O" notation?

Answer 2

複雑さがnで測定される場合、考えられるすべてのnの値を考慮する必要があります。したがって、ほとんどの場合、nは100より大きい。これはn^100が重要でない理由である。

Answer 3

O(n)が漸近的な複雑さであるという事実はありません。より厳密に言えば、n -> infinityとなるとlim(2^n/n^100)を計算することができ、無限大に等しいことがわかるので、漸近的に2^nがn^100より速く成長することを意味します。

Answer 4

big O表記は、漸近的複雑さを記述するために使用されます。単語asymptoticは重要な役割を果たします。漸近は、基本的には、nが3または他の整数ではないことを意味します。 nは無限に大きいと考えるべきです。

n^100が最初に速く成長しても、2^nがn^100を超えて伸びるという点があります。