ランダウの記号（O記法）とは？アルゴリズムの計算量を表す漸近記号の基本を解説

漸近記号（Asymptotic Notations）とは

漸近記号とは、アルゴリズムの計算量を漸近的に評価するために用いられる数学的な表現手法です。入力サイズ n が十分大きくなったときの実行時間やメモリ使用量の増加傾向に着目することで、異なるアルゴリズムの効率性を簡潔に比較できます。一般的によく使われる漸近記号には、主に次の3種類があります。

• O（ビッグオー）記法： 関数の上界（増加率の上限）を表します。
• Ω（オメガ）記法： 関数の下界（増加率の下限）を表します。
• Θ（シータ）記法： 上限・下限の両方を満たす、厳密な増加率を表します。

ビッグオー記法（O記法）の概要

ビッグオー記法は、関数 f(n) の増加が、ある定数倍の範囲で g(n) を超えないこと、すなわち上界を与えるための記法です。アルゴリズムの最悪計算時間を見積もる際に最も広く利用されており、「このアルゴリズムはどれくらい遅くともこれくらいの速さで動作する」という保証を表現できます。

数学的な定義

正の定数 c と n₀ が存在し、n ≥ n₀ を満たすすべての n に対して、次の不等式が常に成り立つとき、f(n) = O(g(n)) と書きます。

0 ≤ f(n) ≤ c · g(n)

これは、「n₀ より右側の領域では、f(n) のグラフが常に c·g(n) のグラフより下（または同じ位置）に収まる」ということを意味します。集合の形で表すと次のように定義されます。

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

代表的な計算量の例

• O(1)： 定数時間 ― 入力サイズに依存しない処理（例：配列要素への直接アクセス）
• O(log n)： 対数時間 ― 二分探索など
• O(n)： 線形時間 ― 線形探索など
• O(n log n)： マージソートやクイックソート（平均ケース）など
• O(n²)： 二乗時間 ― バブルソートなどの単純なソート

まとめ

ランダウの記号（O記法）は、アルゴリズムの計算量を入力サイズに対する増加率として抽象的に捉えるための重要な道具です。上界を示すO記法を中心に、Ω記法やΘ記法を組み合わせて理解することで、アルゴリズムの性能を多面的かつ厳密に分析できるようになります。