[解決済み] Big-O表記とLittle-O表記の違いについて

質問

とはどのような違いがあるのでしょうか？ ビッグ・オー 表記法 O(n) と リトル・オー 表記法 o(n) ?

解決方法は？

f∈O(g)は、本質的には

については 少なくとも1つの 定数の選択 k > 0を求めると、定数 a という不等式がすべてのx > aについて成立するようなものである。

なお、O(g)は、この条件が成立するすべての関数の集合である。

f∈o(g) は、本質的に次のように言っています。

については あらゆる 定数の選択 k > 0を求めると、定数 a という不等式がすべてのx > aについて成立するようなものである。

もう一度、o(g)は集合であることに注意してください。

Big-Oでは、特定の乗数を求めればよいのです k を超えると不等式が成立する。 x .

Little-oでは、最低限なければなりません。 x をどんなに小さくしても、不等式が成り立つようになった後。 k 負や0でない限りは。

どちらも上限を表していますが、やや直感に反して、Little-oの方が強い表現になっています。f∈O(g) の場合、f∈O(g) の場合よりも f と g の成長率に大きな隔たりがあるのです。

格差の説明として、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はより高いレベルのものを含んでいなければなりません。 パワー というように、f(x)とg(x)はxが大きくなるにつれて相対的に離れていくはずである。

純粋に数学の例で言うと（アルゴリズムに言及するのではなく）。

以下は、Big-Oの場合は正しいが、little-oを使った場合は正しくないだろう。

• x² ∈ O(x²)
• x² ∈ O(x² + x)
• x²（O(200*x²)）。

リトル・オーについて、以下のことが言える。

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

f∈o(g) なら、f∈O(g)を意味することに注意。例えば、x² ∈ o(x³) なので、x² ∈ O(x³) も真である（ここでも、Oを <= で、oは < )