Big-O表記O(n)とLittle-O表記の違いは何ですかo(n)?
ベストアンサー1
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 が負またはゼロでない限り、kをどれだけ小さくしても不等式が成立する最小のxが存在する必要があります。
これらは両方とも上限を説明していますが、多少直感に反しますが、Little-o の方がより強い記述です。f ∈ o(g) の場合、f ∈ O(g) の場合よりも f と g の成長率の差がはるかに大きくなります。
この相違点の 1 つの例は次のようになります。f ∈ O(f) は真ですが、f ∈ o(f) は偽です。したがって、Big-O は「f ∈ O(g) は f の漸近的増加が g より速くないことを意味する」と解釈できますが、「f ∈ o(g) は f の漸近的増加が g より確実に遅いことを意味する」と解釈できます。これは<=と のようなものです<。
より具体的には、g(x) の値が f(x) の値の定数倍である場合、f ∈ O(g) は真です。これが、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 を と考えます<)。