2026-08-05·無料·8分で読めます

計算量を1から理解する — オーダー記法は何を測っているのか

O(n)・O(n log n)・O(n²)が実行時間としてどんな体感になるのか。定数倍とオーダーの違い、時間と空間のトレードオフ、そして理論の計算量とプロファイラの実測が食い違う理由まで、前提知識ゼロで解説します。

#complexity #big-o #algorithms #performance #basics

対象textタスクbasics

比喩: 引っ越しの荷物が10倍になったら

段ボール100箱を部屋へ運ぶのに1時間かかったとします。1000箱なら何時間かかるでしょうか。

「10時間」と答えたなら、その作業は箱の数に比例しています。ところが作業の中身が変われば答えも変わります。たとえば「全ての箱の組み合わせについて、中身が重複していないか照合する」なら、比較の回数は箱の数の2乗で増えるので、箱が10倍になれば手間は100倍、つまり100時間です。

計算量の話はこれに尽きます。入力が大きくなったとき、仕事量がどういう形で増えるか。1件あたり何秒かかるかではなく、増え方の「型」を見るのです。

オーダー記法は「速さ」ではなく「増え方」の分類

入力サイズ $n$ に対して必要な手数を $T(n)$ と書きます。 $T(n) = O(f(n))$ の定義はこうです。

T(n) \le c \cdot f(n) \qquad (n \ge n_0)

(1)

平たく言えば、「ある定数倍 $c$ と、ある大きさ $n_0$ をうまく選べば、それ以降はずっと $T(n)$ を $f(n)$ の定数倍で上から押さえられる」ということです。 $c$ は倍率、 $n_0$ は「ここから先の話をしています」という境界線です。

この定義には3つの割り切りが埋め込まれています。オーダー記法は上限しか言わず、定数倍を無視し、十分大きい $n$ だけを見る。

なぜ定数倍を捨てるのでしょうか。同じアルゴリズムでも、言語・CPU・実装の丁寧さで実行時間は簡単に数倍変わります。それを含めた数字は環境ごとの一回限りの値になり、物差しとして使えません。環境をまたいで生き残るのは増え方の型だけ——だからそこだけを名前で呼ぶことにした、という取り決めです。

3つの代表選手を、体の感覚に落とす

粗い見積もりのために「単純な処理をおおよそ毎秒 $10^8$ 回こなす」と仮定します（言語や処理内容で1桁は簡単に動く、あくまで桁感の話です）。

増え方	$n = 10^3$	$n = 10^6$
$O(n)$	一瞬	約0.01秒
$O(n \log n)$	一瞬	約0.2秒
$O(n^2)$	約0.01秒	約3時間
$O(2^n)$	宇宙が終わる	論外

ここで掴んでほしいのは、 $O(n)$ と $O(n \log n)$ の差は実務上ほぼ誤差だということです。 $\log_2 10^6 \approx 20$ なので、係数が20倍つくだけ。対して $O(n^2)$ は $n$ が1000倍になると手間が100万倍になり、質的に別の世界へ行きます。

「ソートは $O(n \log n)$ だからほぼ線形と思ってよい」「二重ループを見たら身構える」という現場の相場観は、この表から来ています。

FIG 1n を動かすと、オーダーの差が「桁」として立ち上がる。縦軸は対数目盛（線形に切り替えると O(2ⁿ) 以外が潰れる理由が分かる）

定数倍とオーダーは別の話 — 小さい $n$ では逆転する

「オーダーが良いほうが速い」は、十分大きい $n$ でのみ成り立つ主張です。

$T_A(n) = 100n$ と $T_B(n) = n^2$ を比べてみます。 $n = 100$ でちょうど並び、それ未満ではオーダーの悪いBのほうが速い。 $n = 10$ なら $T_A = 1000$ 、 $T_B = 100$ で10倍の差です。

これは机上の話ではありません。要素が数十個しかない配列に対して「賢い」データ構造を持ち込むと、ハッシュ計算やポインタ追跡の定数がそのまま乗って、素朴な線形探索に負けます。標準ライブラリのソートが小さい区間だけ挿入ソートに切り替えるのも同じ理由です。オーダーが効いてくる $n$ に自分が本当にいるのかを、まず確認してください。

時間と空間はトレードオフできる

計算量には時間だけでなく空間計算量（使うメモリ量）もあり、同じ記法で測ります。そして多くの場合、この2つは交換できます。

時間をメモリで買うのが、結果を保存して再計算を避けるやり方です。索引を張る、キャッシュを持つ、途中結果をメモ化する。いずれも「表を持てば引くだけで済む」という発想で、動的計画法はこれを最も体系的にやる手法です。

メモリを時間で買う逆方向もあります。深層学習の勾配チェックポイントは、順伝播で計算した中間の値をわざと捨て、逆伝播で必要になったときに計算し直します。計算量は増えますがメモリは劇的に減り、大きなモデルが手元のGPUに載るようになります（誤差逆伝播）。

「速くしたい」と言われたら、まず空いているメモリはないかを考える。これが最初の一手です。

最悪・平均・ならし — どの前提の数字か

同じアルゴリズムでも、前提が違えば数字が変わります。

最悪計算量: どんな入力でもこれ以上悪くならない上限。クイックソートは最悪 $O(n^2)$
平均計算量: 入力がランダムなときの期待値。クイックソートは平均 $O(n \log n)$ で、実務ではこちらが効く
ならし計算量: 連続した操作全体で割った1回あたりのコスト。動的配列の末尾追加は、たまたま容量を拡張する回だけ $O(n)$ かかるが、拡張を倍々でやるのでならせば $O(1)$

ハッシュ表の探索が「 $O(1)$ 」と言われるのも平均の話で、最悪は $O(n)$ です。数字を出すときは、どの前提かを添えないと議論が噛み合いません。

理論とプロファイラが食い違う3つの理由

計算量どおりに直したのに速くならない、あるいは逆に理屈より速い。これは頻繁に起きます。原因はだいたい次の3つです。

1. メモリ階層 オーダー記法は「1手」をすべて同じコストと見なします。しかし実機では、L1キャッシュに載っているデータへのアクセスは数サイクル、主記憶まで取りに行くと数百サイクルかかります。同じ $O(n)$ の走査でも、連続したメモリを舐める配列と、あちこちに散らばったノードを辿る連結リストでは、実測が1桁変わることがあります。「1手」の値段が100倍違うのだから当然です。

2. 分岐予測 現代のCPUは条件分岐の結果を予測して先に進みます。当たればほぼ無コスト、外すと十数サイクル分の作業を捨ててやり直します。ソート済みの配列に対する if が未ソートより速い、という有名な現象はこれです。手数は同じでも、予測しやすさが違う。

3. 定数項と「1手」の中身 メモリ確保、境界チェック、関数呼び出し、動的型付けのオーバーヘッド。 $O(n)$ の $n$ が「ポインタを1つ進める」なのか「オブジェクトを1つ生成する」なのかで、同じ式が指す実時間はまったく違います。

だから作業順序はいつも同じです。まずオーダーを直す（ $n^2$ を $n \log n$ に）。それが済んでから、プロファイラで定数倍を測って削る。 逆順でやると、キャッシュ最適化に丸一日かけた後で「そもそもループが1つ余計だった」と気づくことになります。

手を動かす: 増え方を実測する

オーダーは、 $n$ を倍にして時間が何倍になるかを見れば推定できます。

import time

def timeit(fn, n):
    t = time.perf_counter()
    fn(n)
    return time.perf_counter() - t

def quadratic(n):                  # O(n^2) の代表: 二重ループ
    s = 0
    for i in range(n):
        for j in range(n):
            s += 1

for n in (500, 1000, 2000):        # n を2倍ずつ増やす
    print(n, round(timeit(quadratic, n), 3))

時間が約4倍ずつ増えれば $O(n^2)$ 、約2倍なら $O(n)$ 、2倍より少し多い程度なら $O(n \log n)$ です。要点は3点以上取ること。2点だけだと、定数項に引きずられた比を見て誤診します。

実務で効く4つ

1. まず $n$ を知る 「遅い」と言う前に、扱っている件数を確認します。 $n$ が100で止まるなら、オーダーの議論そのものが不要かもしれません。

2. 二重ループとネストした検索を疑う 性能問題の多くは、リストの中でリストを引いている箇所です。内側の線形探索を辞書（ハッシュ表）に置き換えるだけで $O(n^2)$ が $O(n)$ になります。

3. 推測でなく計測してから削る オーダーを直した後の最適化は、必ずプロファイラの上位から手を付けます。人間のボトルネック予想はよく外れます。

4. 最悪ケースの前提を書き残す 「平均 $O(1)$ 、最悪 $O(n)$ 」の構造は、悪意ある入力や偏ったデータで牙をむきます。どちらの前提で設計したかをコメントに残してください。

まとめ

オーダー記法が測るのは速さではなく増え方。定数倍と小さい $n$ は意図的に捨てている
$O(n)$ と $O(n \log n)$ の差は実務では小さい。 $O(n^2)$ との差は桁が変わる
小さい $n$ ではオーダーの悪いほうが速いことがある。 $T_A = 100n$ と $T_B = n^2$ は $n = 100$ で逆転する
時間と空間は交換できる。メモ化・索引は時間をメモリで買い、勾配チェックポイントはメモリを時間で買う
実測がずれる主因はキャッシュ・分岐予測・定数項。オーダーを直してから、計測して定数を削る

次は、この「増え方」を実際に選び取る道具——配列・ハッシュ・木・ヒープの使い分けを見ます（データ構造の選び方）。