リトルオー記法（o）とは？定義・数式・具体例をわかりやすく解説

リトルオー記法（o）とは

アルゴリズムの計算量を評価するための漸近記法には、ビッグオー（O）、ビッグオメガ（Ω）、ビッグシータ（Θ）がよく知られていますが、これら以外にもいくつかの記法が存在します。そのひとつがリトルオー記法（o）です。

リトルオー記法は、タイトにならない上界（緩い上界）を表すために用いられます。つまり、f(n) が g(n) よりも「厳密に小さい」こと、すなわち両者の増加の度合いが本質的に異なることを表現します。

リトルオー記法の定義

正の実数を扱う2つの関数 f(n)、g(n) を考えます。任意の正の定数 c > 0 に対して、ある整数 n₀ ≥ 1 が存在し、すべての n ≥ n₀ において 0 ≤ f(n) < c・g(n) が成り立つとき、f(n) = o(g(n)) と定義されます。

リトルオー記法の数学的な関係式

この関係を極限を用いて表すと、f(n) = o(g(n)) は次のように書けます。

lim（n → ∞） f(n) / g(n) = 0

これは、n が無限大へ近づくにつれて f(n) と g(n) の比が 0 に収束することを意味します。言い換えると、g(n) の方が f(n) よりも圧倒的に速く増加するということです。

リトルオー記法の具体例

f(n) = n²、g(n) = n³ のとき、f(n) = o(g(n)) が成り立つかどうかを確認してみましょう。

lim（n → ∞） n² / n³ = lim（n → ∞） 1 / n = 0

結果は 0 となり、前述の関係式を満たします。したがって、f(n) = o(g(n)) が成立します。これは、n³ が n² よりも本質的に速く増加することを示しています。

ビッグオー記法（O）との違い

ビッグオー記法は「タイトな上界も含めて」 f(n) ≤ c・g(n) を満たすことを許容しますが、リトルオー記法では、両者が同じオーダーになるような場合は除外されます。

例えば、n² = O(n²) は成り立ちますが、n² = o(n²) は成り立ちません（比が 1 となり、0 に収束しないためです）。この点が両者の大きな違いです。