Big-O 表記と Little-O 表記の違い

Question

違いは何ですか ビッグオー 表記法 O(n) そして リトルオー 表記法 o(n)?

Answer 1

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

のために 少なくとも一つの 定数の選択 k > 0、定数を見つけることができます ある すべての x > a に対して不等式 0 <= f(x) <= k g(x) が成り立ちます。

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

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

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

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

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

Little-o では、最低限のものがあるはずです。 バツ その後、どんなに小さくしても不等式は成り立ちます k, 負またはゼロでない限り。

これらは両方とも上限を説明しますが、多少直感に反しますが、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) が真になります。これが、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²)

little-o には次のことが当てはまります。

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

f ∈ o(g) の場合、これは f ∈ O(g) を意味することに注意してください。例えばx 2 ∈ o(x 3 ) したがって、x 2 ∈ O(x 3 ) も真です (繰り返しますが、O を次のように考えてください) <= そして、として <)

Answer 2

ビッグオーはリトルオーに対して ≤ することです <. 。Big-O は包括的な上限ですが、little-o は厳密な上限です。

たとえば、関数 f(n) = 3n は：

• で O(n²), o(n²), 、 そして O(n)
• ありませんで O(lg n), o(lg n), 、 または o(n)

同様に、数値は 1 は：

• ≤ 2, < 2, 、 そして ≤ 1
• ない ≤ 0, < 0, 、 または < 1

一般的な考え方を示す表を次に示します。

（注記：この表は良いガイドですが、その制限の定義は次の観点から行う必要があります。 上限 通常の制限の代わりに。例えば、 3 + (n mod 2) 3と4の間を永遠に行き来します。入った O(1) 通常の制限がないにもかかわらず、まだ制限があるため、 lim sup: 4.)

Big-O 表記が漸近比較にどのように変換されるかを覚えておくことをお勧めします。比較は覚えやすいですが、n のような言い方ができないため柔軟性が低くなります。^○(1) = P.

Answer 3

私が見つけ、私は概念的について考え、何かを把握することができないときには、の一つがX のXを理解することが有用である（私はちょうどよ、というあなたは試していないと言うことではないを使用する理由ステージを設定する。）

[あなたが知っているもの]アルゴリズムを分類するための一般的な方法は、ランタイムであり、かつ、アルゴリズムのビッグああの複雑さを挙げて、あなたは1が「より良い」となっているかなり良い推定を得ることができます - "を持っている方をOの中で最も小さい」機能！でも、現実の世界では、O（N）は、超大規模な定数などのような愚かな事を除けば、O（N²）よりも「より良い」です。[あなたが知っている/原料]

のは、O（N）で実行されるいくつかのアルゴリズムがありますとしましょう。かなり良い、ハァッ？しかし、あなたは（あなたが華麗な人、あなた）Oで実行するアルゴリズムを思い付くとしましょう（ ^N / <サブ> loglogloglogN ）。わーい！その速いです！あなたの論文を書いているときしかし、あなたは何度も何度も愚かな書き込みを感じると思います。だから、「実際にはO（n）で計算され、この論文では、私は時間O（N）で以前に計算、そのアルゴリズムのXであることが証明された。」あなたは一度それを書き、そしてあなたが言うことができます。

このように、誰もがあなたのアルゴリズムが不明であるどのくらいで---高速であることを知っている、しかし、彼らはその速く知っています。理論的には。 ：）