計算量とBig-O記法 入門 - アルゴリズムの速さを見積もる基礎

「データが少ないときは一瞬なのに、増えた途端に固まる」——そんな処理に出会ったら、それは計算量の問題かもしれません。計算量は、アルゴリズムが入力サイズの増加に対してどれだけ遅く（重く）なるかを見積もるための道具です。この記事では、初中級エンジニア向けに、直感から定義、そして代表的なオーダーまでを、コード例と表で丁寧に整理します。数学的な厳密さよりも「腹落ち」を優先しますが、定義や代表的な計算量の値は Wikipedia や Big-O Cheat Sheet を一次ソースに確認しています。

計算量とは

計算量（complexity）とは、アルゴリズムが必要とする資源の量を、入力サイズ（慣習的に n で表します）の関数として見積もったものです。主に2種類あります。

• 時間計算量（time complexity）: 処理にかかるステップ数（時間）が n に対してどう増えるか
• 空間計算量（space complexity）: 処理に必要な追加メモリが n に対してどう増えるか

ここで大切なのは、計算量が測るのは「秒数」ではなく「増え方」だという点です。同じアルゴリズムでもCPUや言語で実行時間は変わりますが、入力が2倍になったら処理が2倍になるのか、4倍になるのか、それとも変わらないのかという「増え方の形」は、実装環境によらずアルゴリズムそのものの性質として決まります。この「形」を表すのがBig-O記法です。

Big-O 記法の考え方（定数と低次項を捨てる）

Big-O記法は、関数の増加の上限（上界）をおおまかに表す記法です。Wikipediaの定義では、ある正の定数 M が存在して、十分大きな入力に対して常に対象の関数が M × g(n) 以下に収まるとき、その関数は O(g(n)) である、と表現します。厳密には「これ以上のペースでは増えない」という上限の宣言です。

実務で使ううえで押さえるべきコツは、次の2つの単純化です。

• 定数倍を無視する: 2n も 100n も、増え方の形は同じ直線なので、まとめて O(n) と書きます
• 低次の項を捨てる: n^2 + n + 5 は、n が大きくなると n^2 が支配的になるので O(n^2) と書きます

補足: なぜ乱暴に切り捨ててよいのでしょうか。それは、Big-Oが関心を持つのが入力が十分大きくなったときの振る舞い（漸近的な振る舞い）だからです。n が巨大になれば、定数や低次項の影響は相対的に無視できるほど小さくなります。逆に言えば、n が小さいうちはBig-Oの大小がそのまま速さの順にならないこともあります。

代表的なオーダー早見表

まずは全体像を一覧で押さえましょう。右端は「n が1000のときのおおよその操作回数の目安」です（定数倍を無視した概算で、感覚をつかむための数字です）。

上から下へ行くほど、n が増えたときの伸び方が急になります。O(1) と O(log n) はほぼ横ばいで理想的、O(n) と O(n log n) は実用的、O(n^2) は n が数千を超えると苦しくなり、O(2^n) 以降は n が数十でも現実的な時間で終わらなくなります。

O(1)〜O(n!) を具体例で

O(1): 入力が増えても変わらない

配列の要素をインデックスで直接取り出す操作は、配列が10要素でも100万要素でも1回のアクセスで済みます。入力サイズに関係なく一定なので O(1) です。

// O(1): 先頭要素を返すだけ。配列の長さに関係なく一定
function first(arr) {
  return arr[0];
}

O(n): 入力に比例する

配列を1回だけ端から端まで走査する処理は、要素数 n に比例します。要素が2倍になれば、ステップ数もおおよそ2倍です。

// O(n): 合計を求めるために全要素を1回ずつ見る
function sum(arr) {
  let total = 0;
  for (const x of arr) total += x; // n 回のループ
  return total;
}

O(n^2): 二重ループの典型

「すべてのペアを調べる」ような二重ループは O(n^2) になります。次の例は、配列の中に重複があるかを素朴に調べるコードです。

// O(n^2): すべてのペア (i, j) を比較する
function hasDuplicateNaive(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return true; // 内側ループも n に比例
    }
  }
  return false;
}

同じ「重複判定」でも、集合（ハッシュ）を使えば1回の走査で済み、平均 O(n) に改善できます。データ構造を変えるとオーダーが変わるという好例です。

// O(n): 見た値を集合に記録しながら1回だけ走査する
function hasDuplicateFast(arr) {
  const seen = new Set();
  for (const x of arr) {
    if (seen.has(x)) return true; // Set の検索は平均 O(1)
    seen.add(x);
  }
  return false;
}

O(2^n) と O(n!): 全列挙の壁

要素数 n の集合の部分集合の個数は 2^n 個、順列の個数は n! 個あります。これらをすべて生成・チェックするアルゴリズムは、それぞれ O(2^n)、O(n!) になります。n が30を超えるあたりから急速に手に負えなくなり、たとえば巡回セールスマン問題を総当たりで解くと n の増加に対して爆発的に遅くなります。こうした問題では、動的計画法や近似・ヒューリスティックで現実的な計算量に落とし込むのが定石です。

二分探索とO(log n)

O(log n) を体感するのに最適なのが二分探索（binary search）です。ソート済みの配列に対して、真ん中を見て、目的の値が左右どちらにあるかを判断し、探索範囲を毎回半分に絞り込みます。

# O(log n): ソート済み配列から target を二分探索で探す
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid            # 見つかった
        elif arr[mid] < target:
            lo = mid + 1          # 右半分へ
        else:
            hi = mid - 1          # 左半分へ
    return -1                     # 見つからない
 
# 要素100万個でも、半分にする操作は約20回で済む（2^20 は約100万）

範囲を半分にする操作を繰り返すと、n を1になるまで割る回数は「2で何回割れるか」、つまり log2(n) 回です。要素100万個でも約20回、10億個でも約30回で終わります。これが対数時間の強力さです。線形探索なら100万件で最大100万回の比較が必要なので、差は歴然です。

補足: 二分探索が効くのはあらかじめソートされていることが前提です。1回きりの探索のために毎回ソート（O(n log n)）するなら、線形探索のほうが速いこともあります。ソート済みの状態を何度も検索に使い回せるときに真価を発揮します。データベースのインデックスも、内部で木構造を使って似た発想で高速化しています（詳しくはデータベースインデックス入門を参照）。

最悪・平均・償却計算量

同じアルゴリズムでも、入力の内容によって速さは変わります。そこで計算量は、どのケースを見るかで区別します。

• 最悪計算量（worst case）: もっとも運が悪い入力での計算量。Big-Oで語られるのは多くの場合これです
• 平均計算量（average case）: ランダムな入力を仮定したときの平均的な計算量
• 最良計算量（best case）: もっとも運が良い入力での計算量（実務での指標としては弱め）

代表的な例がクイックソートです。平均では O(n log n) と高速ですが、ピボットの選び方が悪いと最悪で O(n^2) まで劣化します。同様にハッシュテーブルの検索は、衝突が少なければ平均 O(1) ですが、すべてのキーが同じ位置に衝突する最悪ケースではO(n) になります。「平均は速いが最悪は遅い」構造は、レイテンシが重要な場面では注意が必要です。

もう一つ重要なのが償却計算量（amortized complexity）です。これは一連の操作全体をならしたときの1操作あたりのコストを指します。代表例は可変長配列（JavaScriptの配列やPythonのlist）への末尾追加です。容量がいっぱいになると内部で確保し直して全要素をコピーするため、その回だけは O(n) かかります。しかし容量を倍々に増やしていくため、コピーの発生頻度は指数的にまばらになり、多数回の追加でならすと1回あたりは償却 O(1) になります。

補足: 償却 O(1) は「毎回必ず速い」ではなく「長い目で見れば1回あたり定数」という意味です。個々の追加操作の中には、たまに O(n) の重いものが混ざります。この違いは、レートリミットのアルゴリズムのように、瞬間的なスパイクが問題になる場面で意識すると役立ちます。

空間計算量

計算量は時間だけの話ではありません。空間計算量は、アルゴリズムが入力とは別に必要とする追加メモリを見積もります。

• O(1) の空間: 入力サイズによらず一定の作業メモリしか使わない（いくつかの変数だけで完結する処理）
• O(n) の空間: 入力に比例した補助データを作る（先ほどの重複判定で使った Set など）
• 再帰の落とし穴: 再帰はコールスタックを消費します。深さ n まで再帰すると、たとえ各段の処理が軽くても O(n) の空間を使い、深すぎるとスタックオーバーフローになります

時間と空間はしばしばトレードオフの関係にあります。ハッシュを使った重複判定は、追加メモリ（空間 O(n)）と引き換えに時間を O(n^2) から O(n) へ縮めました。「メモリを使って時間を買う」という判断は、実務で頻繁に登場します。

実務でどう使うか

計算量を厳密に証明する場面は多くありませんが、設計判断のものさしとして日常的に役立ちます。

• ネストしたループに気づく: 二重ループを書いたら「これは O(n^2) では？ n はどこまで大きくなる？」と一度立ち止まる。n が小さいと分かっているなら O(n^2) でも問題ありません
• データ構造の選択: 「含まれるか」を何度も判定するなら配列（O(n)）ではなく集合やハッシュ（平均 O(1)）を選ぶ、といった判断がオーダーで説明できます
• N+1問題を疑う: ループの中でDBやAPIを呼ぶと、実質 O(n) 回の通信になります。まとめて取得できないかを考えます
• 大量データはページングやカーソルで: 全件を一度にメモリへ載せるとオフセットが増えるほど重くなります。分割取得の設計はページネーション: オフセット vs カーソルで整理しています

注意: 計算量は万能の指標ではありません。n が常に小さいと分かっている処理を、オーダーを下げるためだけに複雑化するのは、可読性を損なうだけで割に合わないことが多いです。まずは素直に書き、プロファイリングでボトルネックを特定してから、そこに計算量の知識を投入するのが健全な順番です。「推測するな、計測せよ」という原則と、計算量による見積もりは、対立ではなく補完の関係です。

Big-Θ と Big-Ω について

最後に、Big-Oの仲間にも軽く触れておきます。Big-Oは上界（これ以上速くは増えない、の上限）を表しますが、次の2つも定義されています。

• Big-Ω（オメガ）: 下界。少なくともこのペースでは増える、という下限
• Big-Θ（シータ）: 上界と下界が一致するとき、つまり増え方をぴったり挟み込めるときに使う

厳密には「マージソートの計算量は Θ(n log n) 」のように書くのが正確ですが、実務や会話では上界のBig-Oで代用することがほとんどです。慣習として O(...) が「だいたいこのオーダー」を指して使われている、と理解しておけば十分です。

まとめ

• 計算量は入力サイズに対する資源の増え方を表す指標で、時間計算量と空間計算量がある
• Big-O記法は定数倍と低次項を捨てて、増え方の形だけを表す
• 代表オーダーは O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!) の順に急になる（大小はインラインコード内で表記しています）
• 二分探索は範囲を半分ずつ絞るので O(log n)。ソート済みが前提
• 同じアルゴリズムでも最悪・平均・償却で計算量は変わる（クイックソートやハッシュテーブルが好例）
• 実務では設計のものさしとして使い、n が小さい場面で過剰な最適化をしないバランス感覚が大切

計算量の感覚が身につくと、コードを書く前に「これはスケールするか」を予測できるようになります。まずは自分が普段書くループやデータ構造が何のオーダーなのかを言葉にすることから始めてみてください。さらに学びたい方は、プログラミング学習におすすめの本も参考にどうぞ。

参考リンク

• Big O notation - Wikipedia
• Time complexity - Wikipedia
• Big-O Cheat Sheet
• Amortized analysis - Wikipedia
• Binary search algorithm - Wikipedia