0

大きなO表記で表現する方法がよくわかりません。私はこれについて話しているいくつかの情報源を見てきましたが、それは私をより不確かにしただけです。big-Oで書くとき、定数を無視する必要がありますか？

例：

1. 0.02N³
2. 4N*log(2^N)
3. 24Nlog(N)
4. N²
5. N*sqrt(N)

これは、「定数を無視する」という意味です。

1. O(N³)
2. O( N*log(2^N) )
3. O( Nlog(N) )
4. O( N² )
5. O( N*sqrt(N) )

O( N*log(2^N) )他の例とO( N*sqrt(N) )比較して、どれくらい速く成長していますか？

私は本当に助けに感謝しますので、事前に感謝します

4

2 に答える 2

4

Big O表記は、関数の漸近的な振る舞いを特徴づけます。数学的f(x) = O(g(x))にいつlim (x->inf) (f(x)/g(x)) = const

明確にしましょう。5つの一般的な表記法（バッハマン-ランダウ表記法）があります。

 ω (small omega)
 Ω (big omega)
 Θ (theta)
 Ο (big o)
 ο (small o)

それらは数学的な比較演算子のように機能します。

 < (strictly less)
 <= (less or equals)
 = (equals)
 >= (greater or equals)
 > (strictly greater)

厳密に言うと、big oは単なる上限であるため、big-o表記だけに基づいてどの関数がより速く成長するかを判断することはできません。

たとえば、クイックソートの最悪の場合の複雑さ= O（n 2 ）ですが、クイックソートの最悪の場合の複雑さ= O（n 889 ）と言うのも正しいことです。x<2という知識に基づいてx<899と言えるのと同じです。

動作が制限されているため、関数の定数と次数の少ない被加数（これらは最上位の被加数によって「支配」されています）を無視できます。たとえば、の場合f(x) = 33*n³ + n² + n + 3544、次のように言うのは正しいですf(x) = O(n³) （さらに、f(x) = Θ(n³)どちらがはるかに有益であるかを言うのは正しいです（Θと呼ばれますtight bound）

于 2013-01-12T16:20:51.907 に答える
0

はい、定数を無視します。また、あなたが元の合計を持っている場合。5n^2 + 2nあなたは最も高い指数で最大の議論をするだけです（これも定数なしで）->ここで：O(n^2)
あなたはそれらの例をうまくやりました。

成長を比較するために、wolframalphaまたは任意のツール描画プロットを使用することをお勧めします。そうすれば、それらがどのように変化するかがわかります。

于 2013-01-12T16:10:49.607 に答える