漸近記号の徹底解説：O()・o()・Ω()・ω()・Θ()の意味と使い分け

漸近記号（Asymptotic Notations）とは

漸近記号は、アルゴリズムの計算量を漸近解析によって表現するための数学的な道具です。入力サイズ n が十分に大きくなったときのアルゴリズムの振る舞いを簡潔に記述できるため、アルゴリズムの効率性を比較・評価する際に欠かせない概念となっています。

代表的な漸近記号には、O（ビッグオー）、Ω（ビッグオメガ）、Θ（ビッグシータ）の3つがあり、さらにそれらの厳密な上限・下限を表す o（リトルオー）や ω（リトルオメガ）も存在します。以下、それぞれの定義と特徴を詳しく見ていきましょう。

ビッグオー記法：O()

ビッグオー（O）記法は、関数 f(n) の上限（上界）を定数倍の範囲で示します。つまり、f(n) の増加率がある関数 g(n) を超えないことを保証するものです。

形式的には、正の定数 c と n₀ が存在し、すべての n ≥ n₀ に対して f(n) ≤ c·g(n) が成り立つとき、f(n) = O(g(n)) と表します。

例えば、線形探索の計算量は O(n)、二分探索は O(log n)、マージソートは O(n log n) と表されます。最悪ケースの実行時間を見積もる際によく用いられます。

リトルオー記法：o()

リトルオー（o）記法は、ビッグオーと同様に上限を表しますが、その上限がタイト（緊密）にならない点が異なります。言い換えれば、f(n) の緩い（loose）上限を表す記法です。

任意の正の定数 c に対して、ある n₀ が存在し、すべての n ≥ n₀ で f(n) < c·g(n) が成り立つとき、f(n) = o(g(n)) となります。ビッグオーとの大きな違いは、「等号成立」が許されないことです。例えば、n = o(n²) は成り立ちますが、n = O(n²) も成り立つのに対し、n = o(n) は成り立ちません。

ビッグオメガ記法：Ω()

ビッグオメガ（Ω）記法は、関数 f(n) の下限（下界）を定数倍の範囲で示します。これは、f(n) の増加率がある関数 g(n) を下回らないことを保証するものです。

形式的には、正の定数 c と n₀ が存在し、すべての n ≥ n₀ に対して f(n) ≥ c·g(n) が成り立つとき、f(n) = Ω(g(n)) と表します。

例えば、比較ベースのソートアルゴリズムは、どのような手法でも最悪 Ω(n log n) の計算量が必要であることが知られており、理論的な限界を示す際に活用されます。

リトルオメガ記法：ω()

リトルオメガ（ω）記法は、リトルオーの下限版にあたる漸近記号で、f(n) の緩い下限を表します。

任意の正の定数 c に対して、ある n₀ が存在し、すべての n ≥ n₀ で f(n) > c·g(n) が成り立つとき、f(n) = ω(g(n)) となります。例えば、n² = ω(n) は成り立ちますが、n = ω(n) は成り立ちません。

ビッグシータ記法：Θ()

ビッグシータ（Θ）記法は、関数 f(n) の増加率を上下両方から挟み込むことで、定数倍の範囲内で厳密に限定します。つまり、上限と下限が一致した「タイトな境界」を与える記法です。

形式的には、正の定数 c₁、c₂ および n₀ が存在し、すべての n ≥ n₀ に対して c₁·g(n) ≤ f(n) ≤ c₂·g(n) が成り立つとき、f(n) = Θ(g(n)) と表します。

例えば、マージソートの計算量は最良・最悪・平均のいずれの場合も Θ(n log n) であり、このように増加率が一意に定まる場合に用いると非常に有用です。

各記法の関係まとめ

これらの記法の関係は、数値の比較における不等号に似ています。

• O(g(n))：f(n) ≤ c·g(n)（上限、≤ に相当）
• o(g(n))：f(n) < c·g(n)（厳密な上限、< に相当）
• Ω(g(n))：f(n) ≥ c·g(n)（下限、≥ に相当）
• ω(g(n))：f(n) > c·g(n)（厳密な下限、> に相当）
• Θ(g(n))：c₁·g(n) ≤ f(n) ≤ c₂·g(n)（相等、= に相当）

アルゴリズムの性能を正確に評価するには、問題の性質に応じて適切な記法を選ぶことが重要です。特に、計算量が上下ともに確定している場合は Θ を、最悪ケースのみを保証したい場合は O を使うのが一般的です。