algorithm - ビッグオー記法を理解する

Question

アルゴリズムに関するいくつかの標準的な本はこれを生成します:

すべてのn > n ₀に対して 0 ≤ f( n ) ≤ c⋅g( n )

big-O を定義する際に、big-O をより正確に視覚化して理解するのに役立つ強力な例を使用して、これが何を意味するのか説明してくれる人はいますか?

Answer 1

関数がf(n)あり、それを分類しようとしているとします。それは他の関数の大きな O ですかg(n)。

定義は基本的に、次のような 2 つの定数 C,N が存在する場合にあるf(n)と述べています。O(g(n))

f(n) <= c * g(n) for each n > N

さて、それが何を意味するのかを理解しましょう。

部品から始めn>Nます - つまり、 の低い値は気にせずn、高い値だけを気にし、(最終的な数の) 低い値が基準に従わない場合は、Nより大きな値を選択することで黙って無視できます。次にそれら。

次の例を見てください。

n: の値が小さい場合はn^2 < 10nlog(n)、2 番目の値がすぐに追いつき、それN=10を取得した後は、すべてn>10の主張10nlog(n) < n^2が正しいことを確認でき10nlog(n)ますO(n^2)。定数は、c定数係数による倍数も許容できることを意味し、それを望ましい動作として受け入れることもできます (たとえば、 が であることを示すの に役立ち5*nますO(n)。c=6 と show を使用して、 inにあることを取得できます。Nn > N5n < nc5n < 6n5nO(n)

Answer 2

この問題は数学の問題であり、アルゴリズムの問​​題ではありません。

ここで定義と良い例を見つけることができます: https://math.stackexchange.com/questions/259063/big-o-interpretation

@トーマスが指摘したように、ウィキペディアにもこれに関する良い記事があります: http://en.wikipedia.org/wiki/Big_O_notation

詳細が必要な場合は、より具体的な質問をしてみてください。