オーダー記法（O記法・ランダウの記号）とは？アルゴリズム計算量の基礎を解説

5月 11, 2026

基礎

プログラミングやアルゴリズムの学習を進めていると、「計算量」や「O（オー）記法」という言葉を頻繁に耳にするようになります。

効率の良いプログラムを書くためには、プログラムがどの程度の時間やメモリを消費するかを客観的に評価する指標が必要です。

そこで用いられるのが、数学的な概念を応用したオーダー記法（ランダウの記号）です。

オーダー記法を理解すれば、データ量が増えた際にプログラムの動作がどのように変化するかを予測できるようになります。

本記事では、ITの基礎知識として不可欠なオーダー記法の仕組みや種類、計算方法について詳しく解説します。

目次 [ close ]

オーダー記法（O記法）とは何か

オーダー記法とは、アルゴリズムの効率性を表すための表記法の一つです。

主に「入力データの数（n）」が増加したときに、処理時間やメモリ消費量がどのような割合で増えていくかを示します。

ドイツの数学者エドムント・ランダウにちなんで「ランダウの記号」とも呼ばれます。

オーダー記法では、細かい計算ステップ数や具体的な実行時間ではなく、「増加の傾向（スケーラビリティ）」に注目します。

例えば、データが100倍になったときに、処理時間が100倍になるのか、それとも1万倍になるのかを判断するために使われます。

表記としては、アルファベットの大文字「O」を用いて、O(n)やO(n^2)のように記述します。

計算量という考え方

オーダー記法で表される指標のことを、一般に「計算量」と呼びます。

計算量には大きく分けて「時間計算量」と「空間計算量」の2種類が存在します。

時間計算量は、アルゴリズムが完了するまでに必要な「処理の手間（ステップ数）」を指します。

空間計算量は、アルゴリズムを実行する際に消費される「メモリ領域の大きさ」を指します。

現代のコンピュータ資源において、特に重要視されるのは処理速度に直結する時間計算量です。

なぜオーダー記法が必要なのか

プログラムの実行速度は、使用するコンピュータのCPU性能やメモリ、OSの状況によって変動してしまいます。

「このプログラムは実行に3秒かかる」と言っても、高性能なPCと古いスマートフォンでは結果が異なるため、絶対的な秒数ではアルゴリズム自体の良し悪しを評価できません。

そこで、ハードウェアの性能に依存しない、アルゴリズムそのものの純粋な効率性を測るための共通言語としてオーダー記法が使われます。

オーダー記法を用いることで、開発者はデータ規模に応じた最適なアルゴリズムを選択できるようになります。

代表的な計算量の一覧と比較

アルゴリズムによって、計算量の増え方は大きく異なります。

ここでは、よく使われるオーダー記法の種類を、効率が良い順に紹介します。

表記（オーダー）	名称	特徴・具体例
`O(1)`	定数時間	データ量に関わらず、常に一定の時間で終わる（配列の要素アクセスなど）。
`O(log n)`	対数時間	データが増えても計算量はあまり増えない（二分探索など）。
`O(n)`	線形時間	データ量に比例して時間が増える（単純なループ、線形探索など）。
`O(n log n)`	対数線形時間	効率的なソートアルゴリズム（クイックソート、マージソートなど）。
`O(n^2)`	二乗時間	データ量の二乗に比例して時間が増える（二重ループ、バブルソートなど）。
`O(2^n)`	指数時間	データが少し増えるだけで爆発的に時間が増える（再帰的なフィボナッチ数列など）。

O(1) ：定数時間

O(1)は、データの件数 n がどれだけ増えても、処理にかかる時間が常に一定であることを示します。

例えば、配列の特定のインデックス（3番目の要素など）を読み取る操作がこれに該当します。

最も理想的で高速なアルゴリズムと言えます。

O(log n) ：対数時間

O(log n)は、処理のたびに探索対象が半分になっていくようなアルゴリズムで現れます。

代表例は、ソート済みのデータから目的の値を探す「二分探索（バイナリサーチ）」です。

データが1,000,000件（100万件）あっても、わずか20回程度のステップで完了するため、非常に効率的です。

O(n) ：線形時間

O(n)は、データ数に比例して処理時間が延びていく状態です。

配列の全要素を一つずつ順番にチェックする「線形探索」や、1重の for 文による処理が典型例です。

データが10倍になれば処理時間も10倍になるという、直感的に分かりやすい計算量です。

O(n log n) ：対数線形時間

O(n log n)は、効率的な並べ替え（ソート）アルゴリズムでよく見られる計算量です。

マージソートやクイックソート（平均時）などがこれに当たります。

O(n)よりは少し遅いですが、次に説明するO(n^2)よりも圧倒的に高速であり、実用的なアルゴリズムの多くがこの範囲を目指して設計されます。

O(n^2) ：二乗時間

O(n^2)は、データ数の二乗に比例して計算量が増加します。

二重のループ処理で、配列の全要素の組み合わせをチェックする場合などに発生します。

データが1,000件程度なら問題ありませんが、100,000件になると処理が極端に重くなり、「フリーズした」と感じるほどの遅延を招くことがあります。

オーダー計算の基本ルール

プログラム全体のオーダーを計算する際には、数学的な厳密さよりも「最も大きな影響を与える部分」に注目します。

以下の3つのルールを覚えることで、簡単にオーダーを導き出せるようになります。

1. 定数倍は無視する

処理の中に「ループが2回あるから 2n」や「最初に初期化で100ステップかかるから n + 100」という計算があったとします。

しかし、オーダー記法では O(2n) や O(n + 100) とは書かず、すべてO(n)として扱います。

データ数 n が無限に大きくなったとき、2倍やプラス100という差は、増加の傾向に比べれば無視できるほど小さいからです。

2. 最も次数の高い項以外は無視する

一つのアルゴリズム内に O(n^2) の部分と O(n) の部分が混在している場合、全体としては O(n^2) と見なします。

例えば n^2 + n という計算式であれば、n が増えるにつれて n^2 の影響が圧倒的に強くなるためです。

複雑な式であっても、一番支配的な（増え方が激しい）項だけを残して簡略化するのがルールです。

3. 最悪の場合（最悪時間計算量）を考える

オーダー記法は通常、「最悪の場合にどれだけ時間がかかるか」を想定して記述します。

例えば、配列から特定の数字を探すとき、運良く1番目に見つかることもあれば、一番最後まで見つからないこともあります。

この場合、最も時間がかかる「最後まで見つからないケース」を基準にして O(n) と表現するのが一般的です。

プログラムコードを用いた計算量の具体例

実際のコードを見ながら、どのようにオーダーを判定するかを解説します。

O(n) の例：リストの合計値計算

リストのすべての要素を足し合わせる処理を考えます。

Python

def calculate_sum(numbers):
    total = 0  # O(1)
    for num in numbers:  # リストの長さnに依存するループ
        total += num  # O(1)
    return total  # O(1)

このコードでは、リストの要素数 n だけ繰り返し処理が行われます。

定数時間の処理が含まれていますが、ループが支配的であるため、この関数の時間計算量は O(n) となります。

O(n^2) の例：重複チェック（二重ループ）

リストの中に重複する数字があるかどうかを確認する素朴な方法です。

Python

def has_duplicate(numbers):
    n = len(numbers)
    for i in range(n):  # 外側のループ
        for j in range(i + 1, n):  # 内側のループ
            if numbers[i] == numbers[j]:  # 比較処理
                return True
    return False

この場合、外側のループが n 回回り、内側のループも n に近い回数だけ回ります。

n × n に近い計算ステップが必要となるため、計算量は O(n^2) と判定されます。

計算量を意識したパフォーマンスチューニング

開発の現場でオーダー記法が重要になるのは、システムのパフォーマンスを改善するときです。

例えば、O(n^2) のアルゴリズムを O(n log n) や O(n) に改善できれば、劇的な速度向上が見込めます。

実務での活用シーン：検索処理

何万件ものユーザーデータから特定のIDを探す際、単純な O(n) の探索（上から順に探す）を行っていると、アクセスが増えたときにサーバーが重くなります。

ここでデータベースの「インデックス」を活用すると、内部的に O(log n) やハッシュを用いた O(1) での検索が可能になります。

「データが増えても重くならない仕組み」を設計するために、オーダー記法の考え方は欠かせません。

実務での活用シーン：ソートの選択

大量のデータを並べ替える際、安易に二重ループのソート（バブルソート等）を使うと、データが10倍になっただけで処理時間は100倍になってしまいます。

標準ライブラリのソート関数を使うと、多くの言語では内部で O(n log n) の高度なアルゴリズムが動くようになっています。

自分でアルゴリズムを実装する場合も、常に「この処理のオーダーはいくつか」を自問することが、プロフェッショナルなエンジニアへの第一歩です。

まとめ

オーダー記法（O記法）は、アルゴリズムの性能を「入力規模に対する処理の増え方」で評価する非常に強力なツールです。

O(1) や O(log n) のように、できるだけ計算量の小さいアルゴリズムを選択することが、効率的なシステム開発の鍵となります。

プログラムを書く際には、「ループが何重になっているか」「データ量が増えたときに破綻しないか」をオーダー記法の視点で見直してみてください。

この基礎知識を身につけることで、単に動くだけでなく、スケーラビリティに優れた高品質なコードを書けるようになるはずです。

アルゴリズムの学習は奥が深いですが、まずは主要なオーダーの形と、計算量の求め方をしっかりとマスターしておきましょう。