漸近表記とは？ビッグオー・ビッグオメガ・ビッグシータの3つの記法を解説

漸近表記（Asymptotic Notations）とは

漸近表記は、アルゴリズムの計算量を漸近解析によって表現するために用いられる数学的なツールです。入力サイズ n に対するアルゴリズムの実行時間やメモリ使用量の増加傾向を厳密に記述することで、アルゴリズムの効率性を客観的に比較・評価することができます。一般的に広く使われている漸近表記には、以下の3種類があります。

ビッグオー記法（Big-Oh Notation）

ビッグオー（O）記法は、関数 f(n) に対して定数倍の範囲で上界（上限）を与える記法です。アルゴリズムの計算量が、どの程度の増加にとどまるかという「最悪時の増加率の上限」を示す際に用いられます。

正の定数 c と n0 が存在し、n0 より右側の領域において f(n) が常に c·g(n) 以下となる場合、f(n) = O(g(n)) と表記します。

O(g(n)) = { f(n) : 正の定数 c と n0 が存在し、すべての n ≥ n0 に対して 0 ≤ f(n) ≤ c·g(n) が成り立つ }

ビッグオメガ記法（Big-Omega Notation）

ビッグオメガ（Ω）記法は、関数 f(n) に対して定数倍の範囲で下界（下限）を与える記法です。アルゴリズムの計算量が、最低でもどの程度の増加を示すかという「増加率の下限」を表します。

正の定数 c と n0 が存在し、n0 より右側の領域において f(n) が常に c·g(n) 以上となる場合、f(n) = Ω(g(n)) と表記します。

Ω(g(n)) = { f(n) : 正の定数 c と n0 が存在し、すべての n ≥ n0 に対して 0 ≤ c·g(n) ≤ f(n) が成り立つ }

ビッグシータ記法（Big-Theta Notation）

ビッグシータ（Θ）記法は、関数 f(n) に対して定数倍の範囲で上下両方の境界（タイトな境界）を与える記法です。アルゴリズムの計算量の増加率を、上限と下限の両面から正確に特徴づけることができます。

正の定数 c1、c2 および n0 が存在し、n0 より右側の領域において f(n) が常に c1·g(n) 以上 c2·g(n) 以下の範囲に収まる場合、f(n) = Θ(g(n)) と表記します。

Θ(g(n)) = { f(n) : 正の定数 c1、c2 および n0 が存在し、すべての n ≥ n0 に対して 0 ≤ c1·g(n) ≤ f(n) ≤ c2·g(n) が成り立つ }

3つの記法のまとめ

ビッグオー（O）は「増加率の上限」、ビッグオメガ（Ω）は「増加率の下限」、ビッグシータ（Θ）は「増加率の上限と下限の両方」を表します。特に Θ 記法は、アルゴリズムの計算量を最も厳密に特徴づけられるため、理論的な解析で重要な役割を果たします。これらの記法を使い分けることで、アルゴリズムの性能を入力サイズの増加に対する振る舞いとして正確に評価できます。