395

Big-O表記O(n)とLittle-O表記の違いは何o(n)ですか?

4

5 に答える 5

517

f ∈ O(g) は本質的に

定数k > 0 の少なくとも 1 つの選択肢について、すべての x > a に対して不等式 0 <= f(x) <= kg(x) が成り立つような定数aを見つけることができます。

O(g) は、この条件が成立するすべての関数の集合であることに注意してください。

f ∈ o(g) は本質的に

定数k > 0 を選択するたびに、すべての x > a に対して不等式 0 <= f(x) < kg(x) が成り立つような定数aを見つけることができます。

繰り返しますが、o(g) は集合であることに注意してください。

Big-O では、不等式が最小xを超えて成立する特定の乗数kを見つけることだけが必要です。

Little-o では、負またはゼロでない限り、kをどれだけ小さくしても不等式が成立する最小のxが存在する必要があります。

どちらも上限を表していますが、直観に反するように、Little-o の方がより強力なステートメントです。f ∈ O(g) の場合よりも f ∈ o(g) の場合の方が、f と g の成長率の差ははるかに大きくなります。

格差の一例は次のとおりです。f ∈ O(f) は true ですが、f ∈ o(f) は false です。したがって、Big-O は、「f ∈ O(g) は、f の漸近成長が g よりも速くないことを意味する」のに対し、「f ∈ o(g) は、f の漸近成長が g より厳密に遅いことを意味する」と読むことができます。<=対のようなもの<です。

より具体的には、g(x) の値が f(x) の値の定数倍である場合、f ∈ O(g) は true です。これが、big-O 表記を使用するときに定数を削除できる理由です。

ただし、f ∈ o(g) が真であるためには、g の式に x のより高いべき乗が含まれている必要があるため、f(x) と g(x) の間の相対的な分離は、x が大きくなるにつれて実際に大きくなる必要があります。

純粋に数学の例を使用するには (アルゴリズムを参照するのではなく):

以下は Big-O に当てはまりますが、little-o を使用した場合は当てはまりません。

  • x² ∈ O(x²)
  • x² ∈ O(x² + x)
  • x² ∈ O(200 * x²)

以下は、little-o に当てはまります。

  • x² ∈ o(x³)
  • x² ∈ o(x!)
  • ln(x) ∈ o(x)

f ∈ o(g) の場合、これは f ∈ O(g) を意味することに注意してください。たとえば、x² ∈ o(x³) なので、x² ∈ O(x³) もまた真です (ここでも、O を<=、o を と考えてください<) 。

于 2009-09-01T20:32:32.360 に答える
234
于 2009-09-01T20:50:27.800 に答える
54

何かを概念的に把握できない場合、なぜ X を使用するのかを考えることは、 Xを理解するのに役立ちます。

知っていること: アルゴリズムを分類する一般的な方法は実行時であり、アルゴリズムの非常に複雑な部分を引用することで、どれが「より優れている」かをかなり正確に見積もることができます。おお！現実の世界でも、O(N) は O(N²) よりも「優れています」。

O(N) で実行されるアルゴリズムがあるとします。かなりいいですね。しかし、あなた (あなたは素晴らしい人です) が O( N ⁄<sub>loglogloglogN)で動作するアルゴリズムを思いついたとしましょう。わーい！その高速！しかし、論文を書いているときにそれを何度も何度も書くのはばかげていると感じるでしょう。つまり、一度書くと、「この論文では、以前は時間 O(N) で計算可能だったアルゴリズム X が、実際には o(n) でも計算可能であることを証明しました」と言うことができます。

したがって、あなたのアルゴリズムがより高速であることは誰もが知っています。理論的に。:)

于 2009-09-02T04:53:42.847 に答える