ビッグオメガ（Ω）記法とビッグシータ（Θ）記法の解説

漸近記法（Asymptotic Notations）とは

漸近記法とは、アルゴリズムの計算量（時間計算量や空間計算量）を漸近解析の観点から表現するための数学的な記法です。入力サイズ n が十分に大きくなったときのアルゴリズムの振る舞いを評価するために用いられ、一般的によく使われる記法には「ビッグオー（O）」「ビッグオメガ（Ω）」「ビッグシータ（Θ）」の3種類があります。

ビッグオメガ（Ω）記法

ビッグオメガ（Ω）記法は、関数 f(n) に対して、定数倍の範囲内での下限（下界）を与える記法です。アルゴリズムの最良ケースにおける実行時間の増加率を表す際などによく使われます。

正の定数 n₀ と c が存在し、n₀ を超えるすべての n に対して f(n) が常に c·g(n) 以上となるとき、f(n) = Ω(g(n)) と表します。

定義式：

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

ビッグシータ（Θ）記法

ビッグシータ（Θ）記法は、関数 f(n) に対して、定数倍の範囲内での上限と下限の両方（厳密な漸近的境界）を与える記法です。f(n) の増加率が g(n) と同じオーダーであることを示します。

正の定数 n₀、c₁、c₂ が存在し、n₀ を超えるすべての n に対して f(n) が常に c₁·g(n) 以上かつ c₂·g(n) 以下（両端を含む）となるとき、f(n) = Θ(g(n)) と表します。

定義式：

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

まとめ

Ω記法は「少なくともこの程度の増加率である」という下限を、Θ記法は「ちょうどこの程度の増加率である」という上下限を表します。これらの記法を適切に使い分けることで、アルゴリズムの効率を厳密かつ簡潔に評価することができます。