Guides
1791 記事 20 ドメイン

計算量オーダー（O記法）とは？アルゴリズムの速さを測る物差し

アルゴリズム

手元のノートPCで動かしたプログラムが、データ100件では一瞬で終わったのに、10万件にした途端に一晩かかって終わらない——プログラムを書いていると、誰もが一度はこの壁にぶつかります。不思議なのは、CPUを2倍速いものに買い替えても状況がほとんど改善しないことです。100件が10万件になると、データは1000倍ですが、待ち時間は100万倍になることがある。この「1000倍が100万倍に化ける」現象を、機械の性能とは切り離して、アルゴリズムそのものの性質として言い当てる道具が計算量オーダーです。

計算量オーダーは、単なる試験問題の記法ではありません。たとえば、100万件のログから特定のIDを探す処理を、先頭から順に見ていく実装（$O(n)$）にするか、ソート済み配列への二分探索（$O(\log n)$）にするか、ハッシュ表（平均 $O(1)$）にするかで、応答時間は数十万倍変わります。あるいは機械学習で、$n$ 個のデータ点すべての間の距離を計算する素朴な近傍探索は $O(n^2)$ なので、$n$ が $10^5$ を超えた瞬間に現実的な時間で終わらなくなり、そこで初めて近似最近傍探索という分野が必要になる理由がわかります。宇宙機の軌道決定でカルマンフィルタを使うときも、状態次元 $n$ に対して行列の逆行列計算が $O(n^3)$ で効くので、状態を増やしすぎるとオンボード計算機に載らなくなる——こうした「設計上の意思決定」の根拠は、ほとんどが計算量オーダーの議論です。

この記事では、$O$・$\Omega$・$\Theta$ の定義を「定数 $c$ と閾値 $n_0$ が存在する」という形で厳密に与えるところから始め、なぜ定数倍と低次項を捨ててよいのかを証明し、実際のコードのループ構造から計算量を数える手順、再帰アルゴリズムの漸化式を解くマスター定理、そして動的配列の push_back が償却 $O(1)$ になるカラクリまでを、ひとつずつ導出します。最後にPythonで実際に実行時間を測り、両対数プロットの傾きから理論通りのオーダーが読み取れることを確かめます。

計算量オーダーは秒数ではなく伸び方を測ることを示す2枚の概念図。左は同じアルゴリズムを4倍速い計算機で動かしてもカーブの形が変わらないこと、右は遅い計算機で動く賢いアルゴリズムが速い計算機の素朴な方法をいずれ追い越すことを表す

左の図が「秒数はアルゴリズムの性質ではない」ことを示しています。計算機を4倍速くすると曲線は縦に4分の1に縮みますが、右上がりの勢い（カーブの形）はまったく変わりません。右の図はその帰結で、遅い計算機で動く賢いアルゴリズムが、速い計算機で動く素朴な方法をある地点で必ず追い越し、それ以降は差が開く一方になります。計算機の性能差は定数倍でしかなく、伸び方の差にはいずれ必ず負ける——これがこの記事全体を貫く主張です。

本記事の内容

  • 計算量オーダーの直感的な意味と、$O$・$\Omega$・$\Theta$・$o$ の厳密な定義
  • 定数倍と低次項を落とす操作が正当である理由の証明
  • 逐次・入れ子・分割統治の3パターンからの計算量の数え方
  • $T(n) = aT(n/b) + f(n)$ に対するマスター定理の3ケースと、再帰木による導出
  • 動的配列の push_back が償却 $O(1)$ になることの証明（集約法・会計法・ポテンシャル法）
  • Pythonで実行時間を計測し、両対数の傾きからオーダーを回帰推定する

前提知識

この記事を読む前に、以下の記事を読んでおくと理解が深まります。

対数と指数の基本的な性質（$\log_a n = \log_b n / \log_b a$ など）、等比級数の和、そして高校程度の極限の扱いを使います。

計算量オーダーとは — 「秒数」ではなく「伸び方」を測る

まず、素朴な疑問から始めましょう。アルゴリズムの速さを比べたいなら、実際に動かして秒数を測ればよいのではないか、と思うかもしれません。ところが、この方法にはどうにもならない欠点があります。同じプログラムでも、CPUが違えば秒数は変わります。コンパイラの最適化オプションでも変わります。プログラミング言語をPythonからC++に変えれば、100倍速くなることも珍しくありません。つまり秒数はアルゴリズムの性質ではなく、環境の性質なのです。

そこで発想を変えます。秒数の絶対値ではなく、「入力が大きくなったとき、時間がどういう勢いで伸びるか」 を測ることにする。この「伸び方」なら、CPUを2倍速くしても変わりません。2倍速いCPUは全部の時間を一律に $1/2$ にするだけで、伸び方の形は同じだからです。

日常のアナロジーで考えてみましょう。荷物を運ぶのに、あなたは「1個運ぶのに1分かかる遅い人」だとします。同僚は「1個30秒で運べる速い人」です。荷物が10個なら、あなたは10分、同僚は5分。同僚の勝ちです。ところがここで、同僚のやり方が「荷物を1個運ぶたびに、それまで運んだ全部の荷物を並べ直す」という手順だったとしましょう。荷物が10個なら並べ直しは大した手間ではありませんが、1000個になると、1000回の運搬それぞれで平均500個を並べ直すことになり、作業量は爆発します。「1個あたり30秒」という定数の速さは、作業量の伸び方の前では無力です。計算量オーダーが測ろうとしているのは、まさにこの「伸び方」のほうです。

もう少し具体的に、配列から目的の値を探す2つの方法を比べます。

方法1（線形探索）: 先頭から順に見ていく。$n$ 個の要素があれば、最悪 $n$ 回の比較が必要です。

方法2（二分探索）: 配列がソート済みなら、真ん中と比較して探索範囲を半分に絞る。これを繰り返すと、範囲は $n \to n/2 \to n/4 \to \cdots$ と縮み、1になるまでの回数は $\log_2 n$ 回です。

$n = 10^6$ のとき、方法1は最悪100万回、方法2は約20回。この差は「CPUを速くする」では絶対に埋まりません。100万対20という開きは、アルゴリズムの構造そのものが生んだ差です。計算量オーダーは、この構造的な差を $O(n)$ と $O(\log n)$ という記号で言い当てます。

ここで大事なのは、$O(n)$ と書いたとき、「1回の比較に何ナノ秒かかるか」という情報は意図的に捨てられている、という点です。捨ててよい理由は、$n$ が十分大きくなれば、定数倍の違いは伸び方の違いに必ず飲み込まれるからです。この「必ず飲み込まれる」を数学的にきちんと言い切るために、$O$ の厳密な定義が必要になります。次の節でそれを与えましょう。

O記法・Ω記法・Θ記法の厳密な定義

O記法 — 「ある定数倍を超えない」という上界

$O$ 記法が主張したいのは、直感的には「$f(n)$ は $g(n)$ とだいたい同じか、それより遅い伸び方をする」ということです。しかし「だいたい」では数学になりません。そこで、次の2つの逃げ道を用意して厳密化します。

  1. 定数倍は許す: $f(n) = 3n$ と $g(n) = n$ は「同じ伸び方」と見なしたい。だから $f \le c\,g$ という形にして、係数 $c$ を自由に選べるようにする。
  2. 小さい $n$ は無視する: $f(n) = n^2$ と $g(n) = 100n$ を比べると、$n \le 100$ では $f \le g$ ですが、$n > 100$ では逆転します。私たちが知りたいのは大きい $n$ の話なので、「ある閾値 $n_0$ から先だけ成り立てばよい」とする。

この2つを式にすると、次の定義になります。

$$ \begin{equation} f(n) = O(g(n)) \iff \exists c > 0,\ \exists n_0 > 0 \ \text{s.t.}\ \forall n \ge n_0,\ 0 \le f(n) \le c\,g(n) \end{equation} $$

日本語で読み下すと、「ある正の定数 $c$ と、ある閾値 $n_0$ をうまく選べば、$n_0$ 以降のすべての $n$ で $f(n)$ が $c\,g(n)$ 以下に収まる」ということです。ポイントは $c$ と $n_0$ が「存在すればよい」だけで、どんなに大きな $c$ を持ってきても構わない点にあります。$c = 10^{100}$ でもよいのです。だからこそ定数倍が無視されます。

具体的に確かめてみましょう。$f(n) = 3n + 7$ が $O(n)$ であることを示します。$n \ge 1$ のとき $7 \le 7n$ ですから、

$$ 3n + 7 \le 3n + 7n = 10n $$

が成り立ちます。したがって $c = 10$, $n_0 = 1$ と取れば定義を満たし、$3n + 7 = O(n)$ です。$c$ の選び方は一意ではありません。$n \ge 7$ に限れば $7 \le n$ なので $3n + 7 \le 4n$ となり、$c = 4$, $n_0 = 7$ でも成立します。$c$ と $n_0$ の組が「ひとつでも見つかればよい」というのが定義の要点です。

f(n)=3n+7 を 10n と 4n という2通りの上界で押さえた図。c=10 なら n0=1 から、c=4 なら n0=7 から不等式が成立することを縦線で示している

赤い実線 $f(n) = 3n+7$ が、青い破線 $10n$ の下に $n \ge 1$ の全域で収まっているのが見えます。一方、緑の一点鎖線 $4n$ は $n < 7$ では $f$ より下にありますが、$n = 7$ を境に $f$ を追い越し、以降はずっと上にあります。$c$ を大きく取れば $n_0$ は小さくでき、$c$ を切り詰めると $n_0$ が右に動く——この $c$ と $n_0$ のトレードオフが、定義の「存在すればよい」という言い回しの実体です。灰色の点線 $g(n) = n$ そのものは $f$ より下ですが、定数倍を許すからこそ $f = O(n)$ と言えることも読み取れます。

Ω記法 — 「ある定数倍を下回らない」という下界

$O$ が上界なら、下界も欲しくなります。「このアルゴリズムはどんなに頑張っても $n^2$ 未満にはできない」といった主張をしたいからです。不等号の向きをひっくり返すだけで定義できます。

$$ \begin{equation} f(n) = \Omega(g(n)) \iff \exists c > 0,\ \exists n_0 > 0 \ \text{s.t.}\ \forall n \ge n_0,\ 0 \le c\,g(n) \le f(n) \end{equation} $$

「$f$ は少なくとも $g$ の定数倍はある」という主張です。比較ソートの計算量が $\Omega(n \log n)$ である、という有名な定理はこの形をしています。

Θ記法 — 上下から挟んで「ぴったり」を言う

$O$ は上界、$\Omega$ は下界。両方が同じ $g$ で成り立つなら、$f$ の伸び方は $g$ と完全に同じ、と言い切れます。

$$ \begin{equation} f(n) = \Theta(g(n)) \iff \exists c_1, c_2 > 0,\ \exists n_0 > 0 \ \text{s.t.}\ \forall n \ge n_0,\ 0 \le c_1 g(n) \le f(n) \le c_2 g(n) \end{equation} $$

f(n)=3n^2+5n+7 を下界 3n^2 と上界 15n^2 が作る帯で挟んだ図。n0=1 以降で両方の不等式が同時に成立し、伸び方が n^2 とぴったり一致することを示す

薄紫の帯が $3n^2$ と $15n^2$ に挟まれた領域で、赤い実線 $f(n) = 3n^2 + 5n + 7$ は $n \ge 1$ の全域でこの帯の内側に留まっています。上の境界に触れないことが $O(n^2)$ を、下の境界を割らないことが $\Omega(n^2)$ を意味し、両方が同時に成り立つので $\Theta(n^2)$ です。帯の幅（$c_1$ と $c_2$ の比）がどれだけ広くても構わない点が重要で、「定数倍を除いて完全に同じ伸び方」という主張が $\Theta$ の中身だとわかります。

つまり $f(n) = \Theta(g(n))$ は「$f(n) = O(g(n))$ かつ $f(n) = \Omega(g(n))$」と同値です。この同値性は定義から直ちに従います。$\Theta$ が成り立てば $c_2$ を使って $O$ が、$c_1$ を使って $\Omega$ が言えます。逆に $O$ と $\Omega$ がそれぞれ $c_2, n_2$ と $c_1, n_1$ で成り立つなら、$n_0 = \max(n_1, n_2)$ とすれば両方の不等式が同時に成り立ちます。

実務では「マージソートは $O(n \log n)$」という言い方をよくしますが、正確に言えばマージソートは $\Theta(n \log n)$ です。$O$ は上界の主張しかしていないので、「マージソートは $O(n^{100})$ である」も論理的には正しい主張になってしまいます（無駄に緩いだけです）。厳密さが要る文脈では $\Theta$ を使いましょう。

o記法・ω記法 — 「明確に小さい／大きい」

$O$ と $\Omega$ は等号を含む（$\le$、$\ge$）不等式でした。等号を含まない厳しい版もあります。

$$ \begin{equation} f(n) = o(g(n)) \iff \forall c > 0,\ \exists n_0 > 0 \ \text{s.t.}\ \forall n \ge n_0,\ 0 \le f(n) < c\,g(n) \end{equation} $$

$O$ では「ある $c$ が存在すれば」でしたが、$o$ では「任意の $c$ に対して」に変わっています。どんなに小さい $c$ を持ってきても、十分大きな $n$ では $f < c g$ になる、ということです。これは $f/g \to 0$ を意味します。同様に $\omega$ は $f/g \to \infty$ に対応します。

$n = o(n^2)$、$\log n = o(n)$、$n^{100} = o(2^n)$ などが成り立ちます。最後の例は「どんなに次数の高い多項式でも、指数関数には必ず負ける」という重要な事実です。

これで4つの記法が揃いました。次は、この定義を使って「定数倍と低次項を落とす」という日常的な操作が、なぜ許されるのかを証明します。

なぜ定数倍と低次項を捨ててよいのか

$3n^2 + 5n + 7 = O(n^2)$ と書けるのは当たり前のように扱われますが、定義に戻って確かめると、なぜそれが許されるのかがはっきりします。

低次項が消える理由

$f(n) = 3n^2 + 5n + 7$ を $n^2$ で押さえたい。鍵になるのは、$n \ge 1$ の範囲では低次の項がすべて最高次の項で上から押さえられるという事実です。$n \ge 1$ のとき $n \le n^2$、そして $1 \le n^2$ ですから、

$$ 3n^2 + 5n + 7 \le 3n^2 + 5n^2 + 7n^2 $$

と、すべての項を $n^2$ に置き換えて上から評価できます。右辺をまとめると

$$ 3n^2 + 5n^2 + 7n^2 = (3 + 5 + 7)\,n^2 = 15 n^2 $$

したがって $c = 15$, $n_0 = 1$ で定義を満たし、$3n^2 + 5n + 7 = O(n^2)$ が示せました。この議論は一般の多項式にそのまま通用します。$f(n) = \sum_{k=0}^{d} a_k n^k$（$a_d > 0$）に対して、$n \ge 1$ では $n^k \le n^d$ なので

$$ f(n) \le \left(\sum_{k=0}^{d} |a_k|\right) n^d $$

となり、$c = \sum_k |a_k|$、$n_0 = 1$ で $f(n) = O(n^d)$ です。係数の絶対値を全部足した数を $c$ にしてしまえばいい——これが「低次項は無視できる」の中身です。

左は f(n)=3n^2+5n+7 の各項が全体に占める割合の積み上げグラフで n が大きいほど 3n^2 が支配的になる様子、右は f と 3n^2 と 15n^2 を重ねた図

左の積み上げグラフは、$f(n) = 3n^2 + 5n + 7$ の中で各項が占める割合を $n$ の関数として描いたものです。$n = 1$ では $3n^2$ の寄与はわずか20%で、定数項7のほうが大きいくらいですが、$n = 10$ で84%、$n = 100$ で98.3%となり、$n$ を増やすほど最高次の項だけが残ります。低次項を捨てるという操作は、この「割合がゼロに向かう」ことを利用しているわけです。右のグラフでは、$f$ が最高次だけの $3n^2$ とほとんど重なりつつ、係数の絶対値の総和で作った $15n^2$ には十分な余裕を持って収まっているのが確認できます。

下界も同様に示せます。$n$ が十分大きければ最高次が支配的になるので、たとえば $3n^2 + 5n + 7 \ge 3n^2$（すべての $n \ge 0$ で成立）から $c_1 = 3$ が取れ、$\Omega(n^2)$ も言えます。上下が揃ったので $3n^2 + 5n + 7 = \Theta(n^2)$ です。

定数倍が消える理由

$f(n) = O(g(n))$ で、$k > 0$ を定数とします。このとき $k f(n) = O(g(n))$ が成り立ちます。証明は一行です。仮定より $n \ge n_0$ で $f(n) \le c\,g(n)$ なので、両辺に $k > 0$ を掛けて

$$ k f(n) \le (kc)\,g(n) $$

新しい定数として $c’ = kc$ を取れば定義を満たします。定数倍は「$c$ に吸収させる」だけで消えるわけです。

この性質から、実行時間を「秒」で測ろうが「クロックサイクル数」で測ろうが「基本演算の回数」で測ろうが、オーダーは変わらないことがわかります。単位の変換は定数倍だからです。オーダーが機種に依存しないのは、この吸収のおかげです。

対数の底が消える理由

もうひとつ、頻繁に使う性質を確かめておきます。$O(\log_2 n)$ と $O(\log_{10} n)$ と $O(\ln n)$ は、すべて同じものです。底の変換公式

$$ \log_a n = \frac{\log_b n}{\log_b a} $$

において $1/\log_b a$ は $n$ に依存しない定数ですから、これは定数倍の違いにすぎません。したがって $O$ の中では底を書く意味がなく、単に $O(\log n)$ と書きます。逆に指数関数では底を省略できません。$2^n$ と $3^n$ は $3^n / 2^n = (3/2)^n \to \infty$ なので定数倍の関係ではなく、$2^n = o(3^n)$ です。

左は log2 n・ln n・log10 n が定数倍の違いしかないことを示すグラフ、右は n^5 と 2^n と 3^n を片対数で比べ n≈22.4 で指数が多項式を追い抜くことを示すグラフ

左のグラフでは3本の対数曲線が同じ形をしていて、$\log_2 n / \ln n = 1.4427$、$\ln n / \log_{10} n = 2.3026$ と、$n$ をどれだけ変えても比が一定のままです。これは定義上の定数倍そのもので、だから $O$ の中では底を書きません。右のグラフはその対比です。$n^5$ は $n \approx 22.4$ までは $2^n$ より上ですが、そこで追い抜かれ、以降は差が指数的に開きます。さらに $3^n$（濃赤の破線）は $2^n$ から見てどんどん離れていきます。対数は底を変えても定数倍、指数は底を変えると別物という非対称が、この2枚で一目でわかります。

和と積の法則

計算量を組み立てるときに使う2つの法則も、定義から素直に出ます。

和の法則: $f_1 = O(g_1)$、$f_2 = O(g_2)$ ならば $f_1 + f_2 = O(\max(g_1, g_2))$。

証明します。$n \ge n_1$ で $f_1 \le c_1 g_1$、$n \ge n_2$ で $f_2 \le c_2 g_2$ とします。$n_0 = \max(n_1, n_2)$、$g = \max(g_1, g_2)$ と置けば、$n \ge n_0$ で

$$ f_1(n) + f_2(n) \le c_1 g_1(n) + c_2 g_2(n) \le c_1 g(n) + c_2 g(n) = (c_1 + c_2)\,g(n) $$

$c = c_1 + c_2$ で定義を満たします。「順番に実行する処理の計算量は、重いほうに支配される」という直感が、これで裏付けられました。

積の法則: $f_1 = O(g_1)$、$f_2 = O(g_2)$ ならば $f_1 f_2 = O(g_1 g_2)$。同じ $n_0$ の取り方で、$f_1 f_2 \le c_1 c_2 g_1 g_2$ となり、$c = c_1 c_2$ で成立します。「入れ子のループの計算量は掛け算になる」の根拠です。

極限による判定法

いちいち $c$ と $n_0$ を探すのは面倒です。多くの場合、極限を計算するほうが速く済みます。

$$ L = \lim_{n \to \infty} \frac{f(n)}{g(n)} $$

が存在するとき、次の対応が成り立ちます。

極限 $L$ 結論
$L = 0$ $f = o(g)$（したがって $f = O(g)$ だが $f \ne \Theta(g)$）
$0 < L < \infty$ $f = \Theta(g)$
$L = \infty$ $f = \omega(g)$（したがって $f = \Omega(g)$）

$0 < L < \infty$ の場合を確かめておきます。極限の定義から、任意の $\varepsilon > 0$ に対してある $n_0$ が存在し、$n \ge n_0$ で $|f/g – L| < \varepsilon$ となります。$\varepsilon = L/2$ と取れば

$$ \frac{L}{2} < \frac{f(n)}{g(n)} < \frac{3L}{2} $$

両辺に $g(n) > 0$ を掛けて $\frac{L}{2} g(n) < f(n) < \frac{3L}{2} g(n)$。これは $c_1 = L/2$、$c_2 = 3L/2$ として $\Theta$ の定義そのものです。

たとえば $f(n) = n \log n$、$g(n) = n^{1.1}$ のとき、$f/g = \log n / n^{0.1} \to 0$（対数は任意の正のべきに負ける）なので $n \log n = o(n^{1.1})$ です。「$n \log n$ は $n^{1.1}$ より確実に軽い」ことが極限ひとつで言えました。

気をつけたい落とし穴

$O$ 記法は便利ですが、記法の慣習が数学的にはやや乱暴なので、次の点は押さえておきましょう。

「$=$」は等号ではありません。 本来 $O(g)$ は「条件を満たす関数の集合」であり、$f = O(g)$ は $f \in O(g)$ と書くのが正しい。この慣習のせいで、$O(n) = O(n^2)$ は正しい（左の集合は右の集合に含まれる）のに、$O(n^2) = O(n)$ は誤り、という非対称が生じます。等号のつもりで両辺を入れ替えてはいけません。

$O$ は上界の主張しかしていません。 「このアルゴリズムの最悪計算量は $O(n^2)$ です」と言われても、それが本当に $n^2$ かかるとは限りません。単に「$n^2$ を超えない」と言っているだけです。「本当に $n^2$ かかる」と言いたいなら $\Theta(n^2)$、あるいは「$n^2$ 未満にはできない」と言いたいなら $\Omega(n^2)$ を使います。「最良でも $O(n \log n)$ である」といった言い回しは誤用で、正しくは「$\Omega(n \log n)$ である」です。

定数が実用性を壊すことがあります。 理論上 $O(n)$ でも、隠れた定数が $10^9$ なら実用にはなりません。実際、行列積の理論的な最良オーダーは $O(n^{2.37})$ 程度まで下がっていますが、定数が巨大すぎて実装は誰も使いません。オーダーは「$n$ が十分大きいときの話」であることを忘れないでください。

$O$ 記法の道具立てが揃いました。次は、実際のコードを前にして、どうやって計算量を数え上げるかに進みます。

計算量の数え方 — 逐次・入れ子・分割統治の3パターン

コードから計算量を求める作業は、突き詰めると「基本演算が何回実行されるかを数える」ことです。この数え上げは、コードの制御構造に応じて3つの型に整理できます。

パターン1: 逐次実行 — 和の法則

処理が上から順に並んでいるだけなら、それぞれの計算量を足し合わせ、和の法則で最大のものを取ります。

def sequential_example(a):
    # ブロック1: O(n)
    total = 0
    for v in a:
        total += v

    # ブロック2: O(n^2)
    pairs = 0
    for i in range(len(a)):
        for j in range(len(a)):
            if a[i] + a[j] == 0:
                pairs += 1

    # ブロック3: O(1)
    return total, pairs, len(a)

全体は $O(n) + O(n^2) + O(1) = O(n^2)$ です。ブロック1をどれだけ高速化しても、ブロック2が生きている限り全体のオーダーは変わりません。最適化するなら一番重いブロックから、という当たり前の指針が、和の法則から導かれます。

パターン2: 入れ子ループ — 積の法則と、変動する内側

入れ子は掛け算です。ただし、内側のループ回数が外側の変数に依存する場合は、単純な掛け算ではなく和として厳密に数える必要があります。バブルソートを例にしましょう。

def bubble_sort(a):
    """バブルソート: 隣り合う要素を比較して交換する"""
    a = list(a)
    n = len(a)
    for i in range(n - 1):            # 外側: n-1 回
        for j in range(n - 1 - i):    # 内側: n-1-i 回（i に依存）
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
    return a

内側のループ回数は $i = 0$ のとき $n-1$ 回、$i = 1$ のとき $n-2$ 回、……と減っていきます。総比較回数は

$$ \sum_{i=0}^{n-2} (n – 1 – i) = (n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2} $$

です。この和は等差数列の和なので、初項と末項の平均に項数を掛けて求まります。展開すると $\frac{1}{2}n^2 – \frac{1}{2}n$ で、最高次は $n^2$。したがってバブルソートは $\Theta(n^2)$ です。「ループが2重だから $n^2$」という雑な数え方でも結論は合いますが、正確には係数 $1/2$ がついた三角形の面積を数えていることになります。

内側の回数が変数の割り算で決まる場合は、まったく違う答えになります。

def harmonic_loop(n):
    """内側が n//i 回まわるループ"""
    count = 0
    for i in range(1, n + 1):
        j = i
        while j <= n:
            count += 1
            j += i          # i の倍数だけ触る
    return count

このとき総回数は $\sum_{i=1}^{n} \lfloor n/i \rfloor \approx n \sum_{i=1}^{n} \frac{1}{i} = n H_n$ です。調和数 $H_n \approx \ln n + \gamma$（$\gamma \approx 0.5772$ はオイラー定数）なので、全体は $\Theta(n \log n)$。2重ループでも $n^2$ とは限らないという好例です。エラトステネスの篩が $\Theta(n \log \log n)$ になるのも、同じ種類の和（素数の逆数和）を数えているからです。

対数が現れるのは、変数が乗除算で更新されるときです。

def log_loop(n):
    """毎回2倍していくループ"""
    count = 0
    j = 1
    while j < n:
        count += 1
        j *= 2          # 加算ではなく乗算
    return count

$j$ は $1, 2, 4, \dots$ と進むので、$2^k \ge n$ となる最小の $k$、つまり $\lceil \log_2 n \rceil$ 回でループを抜けます。「毎回半分にする」「毎回2倍する」を見たら $\log$、と覚えておくとよいでしょう。二分探索が $\Theta(\log n)$ なのも、探索区間が毎回半分になるからです。

三角ループ・調和ループ・倍々ループの実行回数を n を変えて数え上げ、理論式 n^2/2・n ln n・log2 n と両対数で重ねたグラフ

3種類のループの実行回数を実際にカウントし、理論式（破線）を重ねたものです。どの実測点も対応する破線にぴったり乗っていて、$n = 16384$ での調和ループの実測回数は $n \ln n$ の1.016倍でした。注目してほしいのは3本の傾きの差です。三角ループ（赤）は両対数で傾き2、調和ループ（青）は傾きがわずかに1を超える程度、倍々ループ（緑）はほぼ水平——同じ「2重ループ」でも内側の回り方ひとつで、両対数上の傾きが2から1、さらに0近くまで動くことが視覚的に確認できます。

パターン3: 分割統治 — 漸化式を立てる

再帰関数では、ループを数える方法が使えません。代わりに、サイズ $n$ の問題を解く時間 $T(n)$ を、より小さい問題の $T$ で表す漸化式を立てます。

マージソートを見ましょう。

def merge_sort(a):
    """マージソート: 半分に分けて再帰的にソートし、併合する"""
    if len(a) <= 1:
        return list(a)
    mid = len(a) // 2
    left = merge_sort(a[:mid])       # T(n/2)
    right = merge_sort(a[mid:])      # T(n/2)
    return merge(left, right)        # Θ(n)


def merge(L, R):
    """ソート済みの2列を1列に併合する（線形時間）"""
    out = []
    i = j = 0
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            out.append(L[i]); i += 1
        else:
            out.append(R[j]); j += 1
    out.extend(L[i:])
    out.extend(R[j:])
    return out

構造を式にすると、サイズ $n$ の問題は「サイズ $n/2$ の問題を2つ解く」＋「$\Theta(n)$ の併合」なので

$$ \begin{equation} T(n) = 2\,T(n/2) + \Theta(n), \qquad T(1) = \Theta(1) \end{equation} $$

二分探索なら、サイズ $n$ の問題を「サイズ $n/2$ の問題1つ」＋「$\Theta(1)$ の中央値比較」に帰着するので

$$ \begin{equation} T(n) = T(n/2) + \Theta(1), \qquad T(1) = \Theta(1) \end{equation} $$

漸化式は立ちました。問題は、これをどう解くかです。一般形 $T(n) = a\,T(n/b) + f(n)$ を機械的に解く強力な定理があります。次の節でそれを導きましょう。

マスター定理 — 分割統治の漸化式を機械的に解く

再帰木で「どこにコストが溜まるか」を見る

天下りに定理を出す前に、なぜ答えがそうなるのかを再帰木で見ておきます。これを理解すれば、定理の3ケースは丸暗記の対象ではなく、「根が重いか、葉が重いか、釣り合っているか」の3通りしかないという当たり前の話に見えてきます。

$T(n) = a\,T(n/b) + f(n)$（$a \ge 1$、$b > 1$）を考えます。再帰の呼び出し関係を木に描くと、次の構造になります。

  • 深さ0（根）: サイズ $n$ の問題が1個。この階層で払うコストは $f(n)$。
  • 深さ1: サイズ $n/b$ の問題が $a$ 個。この階層のコストは $a \cdot f(n/b)$。
  • 深さ2: サイズ $n/b^2$ の問題が $a^2$ 個。コストは $a^2 f(n/b^2)$。
  • 深さ $i$: サイズ $n/b^i$ の問題が $a^i$ 個。コストは $a^i f(n/b^i)$。

再帰木の模式図。根がサイズ n の問題、深さ1が a 個の n/b、深さ2が a^2 個の n/b^2 で、深さ L=log_b n の葉は n^(log_b a) 個になることを示す

再帰の呼び出し関係を木に描くと、上の箇条書きがそのまま絵になります。下に1段降りるごとに問題の個数は $a$ 倍に増え、サイズは $1/b$ に縮む——この2つの効果のせめぎ合いが、階層ごとのコスト $a^i f(n/b^i)$ を決めています。木の高さは $L = \log_b n$ で $n$ に対して対数的にしか伸びない一方、葉の個数 $a^L = n^{\log_b a}$ は $n$ のべき乗で増えることが図の形からも見て取れます。「幅は爆発するが深さは対数」という非対称が、次に見る3ケースの分かれ目を生みます。

問題サイズが1になるのは $n / b^L = 1$、すなわち $L = \log_b n$ のときです。この最下層（葉）の個数は $a^L = a^{\log_b n}$ 個で、それぞれ $\Theta(1)$ のコストを払います。

ここで $a^{\log_b n}$ を扱いやすい形に直します。両辺の自然対数を取ると

$$ \ln\left(a^{\log_b n}\right) = \log_b n \cdot \ln a = \frac{\ln n}{\ln b} \cdot \ln a = \ln n \cdot \frac{\ln a}{\ln b} = \ln n \cdot \log_b a $$

指数を戻すと、次の重要な等式が得られます。

$$ \begin{equation} a^{\log_b n} = n^{\log_b a} \end{equation} $$

そこで $c_{\text{crit}} = \log_b a$ と置き、これを臨界指数と呼ぶことにします。葉の総コストは $\Theta(n^{c_{\text{crit}}})$ です。以上をまとめると、$T(n)$ は「葉のコスト」＋「各階層で払う $f$ のコストの合計」になります。

$$ \begin{equation} T(n) = \Theta\!\left(n^{c_{\text{crit}}}\right) + \sum_{i=0}^{L-1} a^i f\!\left(\frac{n}{b^i}\right) \end{equation} $$

3ケースが現れる理由 — 等比級数の公比を見る

$f(n) = n^c$（$c \ge 0$）という代表的な場合で、上の総和を計算してみましょう。$f(n/b^i) = (n/b^i)^c = n^c / b^{ci}$ ですから、

$$ \sum_{i=0}^{L-1} a^i \cdot \frac{n^c}{b^{ci}} = n^c \sum_{i=0}^{L-1} \left(\frac{a}{b^c}\right)^i $$

きれいな等比級数になりました。公比を $r = a / b^c$ と置くと、$r$ の大きさによって和の振る舞いが3通りに分かれます。ここが3ケースの正体です。

$r$ と1の大小は、両辺の対数を取れば $c$ と $c_{\text{crit}} = \log_b a$ の大小に翻訳できます。$r > 1 \iff a > b^c \iff \log_b a > c$、つまり $c < c_{\text{crit}}$ です。

(i) $c < c_{\text{crit}}$（$r > 1$）のとき — 葉が重い。 公比が1より大きい等比級数は最後の項が支配的で、$\sum_{i=0}^{L-1} r^i = \frac{r^L – 1}{r – 1} = \Theta(r^L)$ です。$n^c r^L = n^c (a/b^c)^{\log_b n} = n^c \cdot a^{\log_b n} / n^c = n^{c_{\text{crit}}}$ となり、和も葉と同じ $\Theta(n^{c_{\text{crit}}})$。合わせて $T(n) = \Theta(n^{c_{\text{crit}}})$ です。再帰の一番下、無数の小さな問題にコストが溜まっている状態です。

(ii) $c = c_{\text{crit}}$（$r = 1$）のとき — 全階層が同じ重さ。 公比が1なので和は単に項数、すなわち $L = \log_b n$ です。全体は $n^c \cdot \log_b n = \Theta(n^{c_{\text{crit}}} \log n)$。葉のコスト $\Theta(n^{c_{\text{crit}}})$ はこれに飲み込まれます。どの階層でも同じだけ仕事をしていて、階層の数 $\log n$ だけ倍になるという、いちばん美しいケースです。

(iii) $c > c_{\text{crit}}$（$r < 1$）のとき — 根が重い。 公比が1未満なので $\sum_{i=0}^{\infty} r^i = \frac{1}{1-r}$ という定数に収束します。したがって和は $\Theta(n^c) = \Theta(f(n))$。一番上の1回の処理がすべてを支配し、再帰の中身は誤差というケースです。

n=4096 の再帰木について、3ケースそれぞれの階層ごとのコストを対数軸の棒グラフで並べた図。ケース1は右肩上がりで葉が重く、ケース2は全階層が同じ高さ、ケース3は右肩下がりで根が重い

$n = 4096$ の再帰木について、各階層で実際に払うコストを計算して並べたものです。左（公比2.0）は深くなるほど棒が伸び、最下層の葉だけで全体の50%を占めます。中央（公比1.0）は13段すべての棒が同じ高さで、$\log_2 4096 = 12$ 段ぶん同じ仕事を繰り返しているのが一目でわかります。右（公比0.5）は逆に根が最も高く、深さ0だけで全体の50%を担い、下に行くほど半減していきます。マスター定理の3ケースは、この棒グラフが右肩上がりか・平らか・右肩下がりかの3通りにすぎないのです。

この3通りの見立てを一般の $f$ に拡張したものが、マスター定理です。

マスター定理の主張

$a \ge 1$、$b > 1$ を定数、$f(n)$ を正の関数とし、$T(n) = a\,T(n/b) + f(n)$ とします。$c_{\text{crit}} = \log_b a$ と置くと、

ケース1: ある $\varepsilon > 0$ が存在して $f(n) = O\!\left(n^{c_{\text{crit}} – \varepsilon}\right)$ ならば

$$ T(n) = \Theta\!\left(n^{c_{\text{crit}}}\right) $$

ケース2: ある $k \ge 0$ が存在して $f(n) = \Theta\!\left(n^{c_{\text{crit}}} \log^k n\right)$ ならば

$$ T(n) = \Theta\!\left(n^{c_{\text{crit}}} \log^{k+1} n\right) $$

ケース3: ある $\varepsilon > 0$ が存在して $f(n) = \Omega\!\left(n^{c_{\text{crit}} + \varepsilon}\right)$ であり、かつ正則条件 $a f(n/b) \le c\,f(n)$（ある $c < 1$ と十分大きな $n$ について）を満たすならば

$$ T(n) = \Theta(f(n)) $$

ケース1とケース3で $\varepsilon$ が要るのは、「多項式的に小さい／大きい」という条件を課すためです。単に $f < n^{c_{\text{crit}}}$ では足りず、$n^{\varepsilon}$ 倍の差がないと等比級数の議論が効きません。ケース3の正則条件は、「1段下りると $f$ の総量が確実に $c$ 倍（$c<1$）に減る」ことを保証していて、これがないと $\sum r^i$ が収束する保証がなくなります。

具体例で使ってみる

マージソート: $T(n) = 2T(n/2) + \Theta(n)$。 $a = 2$、$b = 2$、$f(n) = n$。臨界指数は $c_{\text{crit}} = \log_2 2 = 1$。$f(n) = n = n^1 = n^{c_{\text{crit}}} \log^0 n$ なので、$k = 0$ でケース2に当たります。したがって

$$ T(n) = \Theta\!\left(n^1 \log^{0+1} n\right) = \Theta(n \log n) $$

マージソートは $\Theta(n \log n)$ と結論できました。念のため、展開法でも確かめておきます。$T(n) = 2T(n/2) + n$ を右辺に代入し続けると、

$$ T(n) = 2\left(2T(n/4) + \frac{n}{2}\right) + n = 4T(n/4) + 2n $$

$T(n/4)$ にも同じ操作をすると $T(n) = 8T(n/8) + 3n$。ここまでのパターンから、$k$ 回展開したときの形が読み取れます。

$$ T(n) = 2^k\,T\!\left(\frac{n}{2^k}\right) + k\,n $$

$n/2^k = 1$、つまり $k = \log_2 n$ で再帰が止まります。これを代入すると $2^{\log_2 n} = n$ と $T(1) = \Theta(1)$ より

$$ T(n) = n \cdot \Theta(1) + n \log_2 n = \Theta(n \log n) $$

マスター定理と一致しました。

二分探索: $T(n) = T(n/2) + \Theta(1)$。 $a = 1$、$b = 2$、$f(n) = 1$。臨界指数は $c_{\text{crit}} = \log_2 1 = 0$ なので、$n^{c_{\text{crit}}} = n^0 = 1$。$f(n) = 1 = n^0 \log^0 n$ なので $k = 0$ のケース2です。

$$ T(n) = \Theta\!\left(n^0 \log^1 n\right) = \Theta(\log n) $$

二分探索は $\Theta(\log n)$。展開法で確かめると $T(n) = T(n/2) + 1 = T(n/4) + 2 = \cdots = T(n/2^k) + k$ で、$k = \log_2 n$ のとき $T(n) = T(1) + \log_2 n = \Theta(\log n)$。一致します。

素朴な分割統治の行列積: $n \times n$ 行列を4つの $n/2 \times n/2$ ブロックに分けると、積は8個の小行列積と $\Theta(n^2)$ の加算になります。$T(n) = 8T(n/2) + \Theta(n^2)$。 $c_{\text{crit}} = \log_2 8 = 3$、$f(n) = n^2 = n^{3-1}$ なので $\varepsilon = 1$ でケース1。$T(n) = \Theta(n^3)$。分割しても素朴なやり方では $n^3$ から改善しないことがわかります。

シュトラッセンのアルゴリズム: 巧妙な組み合わせで小行列積を8個から7個に減らします。$T(n) = 7T(n/2) + \Theta(n^2)$。 $c_{\text{crit}} = \log_2 7 \approx 2.807$。$f(n) = n^2 = n^{2.807 – 0.807}$ なので $\varepsilon = 0.807$ でケース1が使えて

$$ T(n) = \Theta\!\left(n^{\log_2 7}\right) \approx \Theta(n^{2.807}) $$

掛け算を1個減らしただけで指数が $3$ から $2.807$ に下がる——再帰の分岐数 $a$ が指数を直接支配していることが、$c_{\text{crit}} = \log_b a$ という式からはっきり読めます。

ケース3の例: $T(n) = 2T(n/2) + n^2$。 $c_{\text{crit}} = 1$、$f(n) = n^2 = n^{1+1}$ なので $\varepsilon = 1$。正則条件を確認すると、$a f(n/b) = 2 (n/2)^2 = n^2/2 = \frac{1}{2} f(n)$ なので $c = 1/2 < 1$ で成立。よって $T(n) = \Theta(n^2)$。再帰の中身は無視できて、一番上の1回の $n^2$ がすべてです。

マスター定理が使えない場合

万能ではありません。ケース1とケース3の「多項式的な差」の条件が満たされない隙間が存在します。たとえば

$$ T(n) = 2T(n/2) + \frac{n}{\log n} $$

は $c_{\text{crit}} = 1$ で $f(n) = n/\log n$。これは $n^1$ より小さいものの、$n^{1-\varepsilon}$ よりは大きいので、ケース1にもケース2にも当てはまりません（答えは $\Theta(n \log \log n)$ です）。

また、分割の仕方が不揃いな場合も対象外です。中央値の中央値法（median of medians）の $T(n) = T(n/5) + T(7n/10) + \Theta(n)$ のような漸化式は、部分問題のサイズが揃っていないのでマスター定理では扱えません。この種の一般形には Akra–Bazzi の定理という拡張があり、上の例では $T(n) = \Theta(n)$ が得られます。なお $1/5 + 7/10 = 9/10 < 1$ となっていて、各階層のコスト合計が公比 $9/10$ の等比級数になるのが $\Theta(n)$ になる理由です。ケース3と同じ「根が重い」構造ですね。

なお、実際のコードでは $n$ が奇数のとき $n/2$ が整数になりません。厳密には $T(\lfloor n/2 \rfloor)$ と $T(\lceil n/2 \rceil)$ を扱う必要がありますが、床関数・天井関数の影響は結論のオーダーを変えないことが知られています。安心して $n/b$ と書いて構いません。

再帰の計算量は片付きました。しかし現実のデータ構造には、「毎回は速いが、たまに非常に重い操作が混じる」という、これまでの枠組みでは評価しにくいものがあります。次はそれを扱います。

償却計算量 — 動的配列のpush_backはなぜO(1)なのか

「たまに重い」をどう評価するか

Pythonのリストに append するとき、あなたは何も気にしていないはずです。しかし内部では、要素を格納する連続領域（バッファ）の容量が有限で、満杯になったら新しい大きな領域を確保し、既存の全要素をコピーする、という重い処理が走ります。この再確保が起きた回の append は $\Theta(n)$ かかります。

すると、素朴には「append の最悪計算量は $O(n)$」となります。$n$ 回 append すれば $O(n^2)$——本当でしょうか。

ここで償却計算量（amortized complexity） の出番です。発想は家計簿に似ています。年に一度の車検で10万円かかるからといって「毎月の車の維持費は10万円」とは言いません。年間の総費用を12で割って月あたりの平均を出します。同じように、$n$ 回の操作にかかった総コストを $n$ で割った値を、1回あたりの償却コストと定義するのです。

重要なのは、償却計算量は「平均計算量」とは違うということです。平均計算量は入力の確率分布に対する期待値ですが、償却計算量は確率を一切使いません。どんな操作列に対しても、総コストが必ず $O(n)$ に収まることを保証する、決定的な主張です。

集約法による証明 — 倍々拡張の総コストを数える

動的配列の典型的な実装では、容量が満杯になったときに容量を2倍にします。初期容量を1として、空の配列に $n$ 回 push_back したときの総コストを数えましょう。

再確保が起きるのは、要素数がちょうど $1, 2, 4, 8, \dots$ に達した直後、つまり2のべき乗のタイミングです。$i$ 番目の push_back で再確保が起きる条件は $i-1$ が2のべき乗のとき、そのコピー量は $i – 1$ 要素分です。したがってコピーの総量は

$$ \sum_{k=0}^{\lfloor \log_2 n \rfloor} 2^k $$

これは公比2の等比級数なので、公式 $\sum_{k=0}^{m} 2^k = 2^{m+1} – 1$ を使うと

$$ \sum_{k=0}^{\lfloor \log_2 n \rfloor} 2^k = 2^{\lfloor \log_2 n \rfloor + 1} – 1 < 2 \cdot 2^{\log_2 n} = 2n $$

途中で $2^{\lfloor \log_2 n \rfloor} \le n$ を使いました。コピーの総量は $2n$ 未満です。これに、各 push_back が必ず行う「1要素の書き込み」$n$ 回分を足すと、総コストは

$$ T_{\text{total}}(n) < n + 2n = 3n $$

したがって1回あたりの償却コストは $T_{\text{total}}(n)/n < 3 = O(1)$。動的配列の push_back は償却 $O(1)$ です。

上段は push_back 70回ぶんの実コストの棒グラフと累積平均、下段はポテンシャル Φ=2s-m の推移。再確保の回だけコストが跳ね上がるが平均は3を超えず、溜めたポテンシャルがコピー費用を相殺する

上段の水色の棒が1回ごとの実コストです。ほとんどの回は高さ1ですが、要素数が $1, 2, 4, 8, 16, 32, 64$ に達した直後だけ全要素コピーで跳ね上がり、65回目には65という突出した値になります。ところが赤い線（そこまでの平均コスト）は緑の破線 $3$ を一度も超えず、70回時点で2.81、途中の最大でも2.95に収まっています。下段はポテンシャル $\Phi = 2s – m$ の推移で、再確保と再確保のあいだにじわじわ溜まった値が、再確保の瞬間にストンと落ちています。この落差がちょうどコピー費用を賄っている——ポテンシャル法の証明が絵になったのがこの下段です。

この証明の心臓部は、等比級数の和が「最後の項の定数倍」で押さえられることです。$1 + 2 + 4 + \cdots + 512 + 1024 = 2047$ で、最後の1024の約2倍にしかならない。過去に払ったコストの合計が、直近の1回の定数倍で済む——これが倍々拡張の魔法です。

会計法 — 「前払い」で理解する

同じ結論を、別の見方で確かめておくと納得が深まります。会計法（accounting method）では、各操作に実際のコストとは違う「請求額」を設定し、余った分を貯金して、後の重い操作の支払いに充てます。

push_back 1回につき3単位を請求することにします。使い道は次の通りです。

  1. 1単位: 今まさに書き込む自分自身のコスト。
  2. 1単位: 将来、次の再確保で自分がコピーされるときのために貯金。
  3. 1単位: 「相棒」の分の貯金。

3番目が要点です。容量 $m$ から $2m$ への再確保が起きた直後を考えます。この時点で配列には $m$ 個の要素があり、次の再確保は要素数が $2m$ になったときです。つまり新しく追加される $m$ 個の push_back が発生する間に、$2m$ 個分のコピー費用を貯めなければなりません。1回につき2単位（上の2番と3番）貯金すれば、$m$ 回で $2m$ 単位が貯まり、ちょうど足ります。したがって請求額3単位で赤字になりません。

請求額が定数（3単位）で、かつ貯金が尽きないなら、$n$ 回の総請求額は $3n$。実際の総コストはこれを超えないので、償却コストは $O(1)$ です。集約法と同じ「3」という定数が出てくるのが気持ちいいところです。

ポテンシャル法 — 状態関数で機械的に示す

最も汎用性が高いのがポテンシャル法です。データ構造の状態 $D$ に対してポテンシャル関数 $\Phi(D) \ge 0$ を定め、$i$ 番目の操作の償却コストを

$$ \hat{c}_i = c_i + \Phi(D_i) – \Phi(D_{i-1}) $$

と定義します（$c_i$ は実コスト）。この定義の下で、総償却コストは総実コストの上界になります。実際、$n$ 回分を足すと中間項が次々に打ち消し合い（望遠鏡和）、

$$ \sum_{i=1}^{n} \hat{c}_i = \sum_{i=1}^{n} c_i + \Phi(D_n) – \Phi(D_0) $$

$\Phi(D_0) = 0$、$\Phi(D_n) \ge 0$ とすれば $\sum \hat{c}_i \ge \sum c_i$ が言えます。償却コストの合計を押さえれば、実コストの合計も押さえられるわけです。

動的配列では、要素数 $s$、容量 $m$ に対して

$$ \Phi = 2s – m $$

と取ります（$s \ge m/2$ の間は非負）。2つの場合を確かめます。

(a) 再確保が起きない場合: 実コスト $c_i = 1$（書き込み1回）。$s$ が1増え、$m$ は不変なので $\Delta\Phi = 2$。よって

$$ \hat{c}_i = 1 + 2 = 3 $$

(b) 再確保が起きる場合: 直前は $s = m$ で満杯。実コストは「$m$ 要素のコピー」＋「1要素の書き込み」で $c_i = m + 1$。操作後は $s’ = m+1$、$m’ = 2m$ なので

$$ \Phi_{\text{after}} = 2(m+1) – 2m = 2, \qquad \Phi_{\text{before}} = 2m – m = m $$

$\Delta\Phi = 2 – m$ を使うと

$$ \hat{c}_i = (m + 1) + (2 – m) = 3 $$

どちらの場合も償却コストはぴったり3になりました。重い再確保のコスト $m$ が、それまでに溜めたポテンシャル $m$ で完全に相殺される様子が、式の上ではっきり見えます。したがって償却 $O(1)$ です。

なぜ「倍々」でなければならないのか

ここで自然な疑問が湧きます。容量を2倍にするのではなく、「毎回100要素ずつ増やす」ではダメなのでしょうか。定数増分 $\delta$ で拡張する場合を計算してみましょう。

再確保が起きるのは要素数が $\delta, 2\delta, 3\delta, \dots$ に達したときで、$k$ 回目の再確保でコピーする量は $k\delta$ です。$n$ 回の push_back では約 $n/\delta$ 回の再確保が起きるので、コピーの総量は

$$ \sum_{k=1}^{n/\delta} k\delta = \delta \cdot \frac{(n/\delta)(n/\delta + 1)}{2} \approx \frac{n^2}{2\delta} $$

総コストが $\Theta(n^2)$、1回あたりの償却コストが $\Theta(n)$ になってしまいました。等差数列の和は $n^2$ のオーダーになるので、いくら $\delta$ を大きくしても（定数である限り）オーダーは救えません。等比か等差かという違いが、$O(1)$ と $O(n)$ という決定的な差を生むわけです。

一般に成長率 $r > 1$（容量を $r$ 倍にする）なら、コピーの総量は公比 $r$ の等比級数で

$$ \sum_i r^i \approx \frac{r}{r-1}\,n $$

となり、$r > 1$ である限り必ず $O(n)$、すなわち償却 $O(1)$ です。ただし係数 $r/(r-1)$ は $r$ が1に近づくと発散します。$r = 2$ なら $2n$、$r = 1.5$ なら $3n$、$r = 1.125$ なら $9n$。

左は倍々拡張と定数増分拡張のコピー総数を両対数で比べた図、右は成長率 r=2・1.5・1.125 と定数増分について1回あたりのコピー要素数を比べた図

左のグラフでは、倍々拡張（青）が理論上界 $2n$ の破線に沿って傾き1で伸びるのに対し、100要素ずつ増やす方式（赤）は傾き2、つまり $\Theta(n^2)$ で伸びています。赤い実測が $n$ を大きくするほど理論式 $n^2/(2\delta)$ の破線に寄っていく点にも注目してください。右のグラフは同じデータを1回あたりに直したもので、$r = 2$ なら1〜2、$r = 1.5$ なら2〜3、$r = 1.125$ なら8〜9のあたりで横ばいになり、いずれも点線で示した理論値 $r/(r-1)$（それぞれ2、3、9）の近くに張り付きます。一方、定数増分だけが右上がりの直線を描き、$n$ に比例して悪化していきます。成長率が定比でありさえすれば係数が変わるだけ、定数増分にした瞬間にオーダーが壊れるという差が、この2枚に凝縮されています。

この係数はメモリの無駄とのトレードオフになっています。$r = 2$ は再確保直後に最大50%の領域が未使用ですが、$r = 1.125$ なら無駄は最大12.5%です。実際、CPythonのリストは new_allocated = newsize + (newsize >> 3) + 6 という式で容量を決めており、これは約1.125倍成長にあたります。コピー回数は倍々より多くなりますが、メモリ効率を優先した設計判断です。後ほどPythonで、この1.125という比を実測で確認します。

償却計算量の道具立ても揃いました。ここまでは主に「最悪の場合」を暗黙に想定してきましたが、最悪・平均・最良の区別と、$O$・$\Omega$ の使い分けを整理しておきましょう。

最悪・平均・最良と、下界の議論

計算量を語るとき、「どの入力に対する話か」を明示しないと混乱します。3つの立場があります。

  • 最悪計算量: サイズ $n$ のすべての入力のうち、最も時間がかかるもの。$T_{\text{worst}}(n) = \max_{|x| = n} T(x)$。
  • 平均計算量: 入力の確率分布を仮定した期待値。$T_{\text{avg}}(n) = E_{x}[T(x)]$。
  • 最良計算量: 最も速いもの。実務ではあまり役に立ちません。

クイックソートが好例です。ピボットが毎回最小値または最大値になると、分割が $1$ と $n-1$ に偏り、$T(n) = T(n-1) + \Theta(n)$ から $\Theta(n^2)$ になります（最悪）。一方、ピボットをランダムに選べば、期待値としては $\Theta(n \log n)$ になります（平均）。すでにソート済みの配列に対して先頭をピボットに選ぶ実装が突然遅くなるのは、この最悪ケースを引いてしまうからです。

ここで $O$ と $\Omega$ の使い分けを整理します。よくある誤解は「$O$ は最悪、$\Omega$ は最良」というものですが、これは間違いです。$O$ と $\Omega$ は「関数の上界／下界」の記法であり、「最悪／最良」は「どの入力を見るか」の話。両者は直交する概念です。「クイックソートの平均計算量は $\Theta(n \log n)$」も「クイックソートの最悪計算量は $\Theta(n^2)$」も、どちらも $\Theta$ を使って言えます。

$\Omega$ が本領を発揮するのは、問題そのものの下界を主張するときです。有名な例が比較ソートの下界です。

要素どうしの比較だけで並べ替えるアルゴリズムを、決定木として捉えます。各内部ノードが「$a_i < a_j$?」という比較、各葉が「この順列が答え」という出力です。$n$ 個の要素の並べ方は $n!$ 通りあり、そのすべてを区別できなければならないので、葉は少なくとも $n!$ 個必要です。高さ $h$ の二分木の葉は最大 $2^h$ 個なので

$$ 2^h \ge n! \quad \Longrightarrow \quad h \ge \log_2 (n!) $$

スターリングの近似 $n! \approx \sqrt{2\pi n}\,(n/e)^n$ の対数を取ると

$$ \log_2 (n!) = n \log_2 n – n \log_2 e + O(\log n) = \Theta(n \log n) $$

木の高さは最悪の比較回数そのものですから、比較に基づくソートは $\Omega(n \log n)$ 回の比較を必要とすると結論できます。マージソートやヒープソートは $\Theta(n \log n)$ なので、この下界を達成する最適なアルゴリズムだとわかります。「これ以上は原理的に速くならない」と言い切れるのが、下界の議論の強みです。

なお、比較以外の情報を使えばこの下界を回避できます。基数ソートや計数ソートが $\Theta(n)$ で動くのは、値そのものをインデックスとして使い、比較モデルの外に出ているからです。下界は「モデル」に対して成り立つという点は覚えておきましょう。

オーダーの階層と、その実感

主要なオーダーを、伸び方の遅い順に並べておきます。

$$ O(1) \subset O(\log n) \subset O(\sqrt{n}) \subset O(n) \subset O(n \log n) \subset O(n^2) \subset O(n^3) \subset O(2^n) \subset O(n!) $$

数字で実感してみましょう。1秒に $10^9$ 回の基本演算ができる計算機を仮定します。

$n$ $\log_2 n$ $n$ $n \log_2 n$ $n^2$ $n^3$
$10^3$ 10 ns 1 μs 10 μs 1 ms 1 秒
$10^6$ 20 ns 1 ms 20 ms 16.7 分 31.7 年
$10^9$ 30 ns 1 秒 30 秒 31.7 年 $3.2\times10^{10}$ 年

log2 n・n・n log2 n・n^2・n^3・2^n の所要時間を両対数で描き、1秒・1分・1時間・1日・1年・100年の水平線を重ねた図

上の表を図にしたものです。灰色の水平線が「1秒」「1分」「1日」「1年」といった実感のある時間の目安で、各オーダーの曲線がその線を横切る $n$ が、そのアルゴリズムの実用限界にあたります。$n = 10^6$ の縦線（一点鎖線）に沿って読むと、$n \log n$ は約0.02秒、$n^2$ はちょうど1000秒（約16.7分）、$n^3$ は1年線をはるかに超えた位置にあります。黒い破線の $2^n$ だけが桁違いに立ち上がっていて、$n$ が数十の時点で1年線を突き抜けているのも見逃せません。

$n = 10^6$ の行を見てください。$n \log n$ なら20ミリ秒で終わる処理が、$n^2$ になると16.7分。$n^3$ に至っては31.7年です。$n$ が100万を超える世界では、$n^2$ のアルゴリズムは実質的に「動かない」と考えるべきだとわかります。

指数関数はさらに極端です。$2^{100} \approx 1.27 \times 10^{30}$ 回の演算は、$10^9$ 回/秒でも約 $4.0 \times 10^{13}$ 年——宇宙の年齢（138億年）の約2900倍です。巡回セールスマン問題を全順列で解こうとすると、都市数20で $20! \approx 2.43 \times 10^{18}$ 通り、これでも約77年かかります。指数時間のアルゴリズムは、$n$ が数十の時点で破綻する。だからこそ近似アルゴリズムやヒューリスティクスが必要になるのです。

理論は出揃いました。ここからは実際にPythonで時間を測り、これらのオーダーが本当に観測できるのかを確かめます。

Pythonでの実装 — 実測時間からオーダーを読み取る

理論上のオーダーが、実際の実行時間に本当に現れるのかを確かめましょう。方針はこうです。

  1. 線形探索・二分探索・バブルソート・マージソートを実装する。
  2. $n$ を変えながら実行時間を測る。
  3. 両対数プロットの傾きを回帰で求め、理論のオーダーと突き合わせる。
  4. 理論曲線を実測に重ねて、形が一致するかを見る。
  5. 定数倍の違いで、小さい $n$ では「オーダーが悪いほうが速い」逆転が起きることを確認する。

3番目がこの実験の核心です。$T(n) \approx C n^p$ なら、両辺の対数を取ると

$$ \log T = p \log n + \log C $$

となり、両対数グラフ上で直線になり、その傾きがちょうど指数 $p$ になります。定数 $C$ は切片に押し込まれて傾きに影響しません。まさに「定数倍を無視してオーダーだけを見る」操作を、グラフ上で実行していることになります。

アルゴリズムの実装

まず4つのアルゴリズムを素直に実装します。

import time
import math
import random
import numpy as np
import matplotlib
import matplotlib.pyplot as plt

# 日本語フォント設定
for cand in ["Hiragino Sans", "Yu Gothic", "Noto Sans CJK JP", "IPAexGothic", "Meiryo"]:
    if any(cand == f.name for f in matplotlib.font_manager.fontManager.ttflist):
        plt.rcParams["font.family"] = cand
        break
plt.rcParams["axes.unicode_minus"] = False

random.seed(0)


def linear_search(a, x):
    """線形探索: 先頭から順に比較する O(n)"""
    for i, v in enumerate(a):
        if v == x:
            return i
    return -1


def binary_search(a, x):
    """二分探索: ソート済み配列を半分に絞り込む O(log n)"""
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == x:
            return mid
        elif a[mid] < x:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

線形探索は入力を1回なめるだけ、二分探索は探索区間を毎回半分にします。この「なめる」と「半分にする」の違いが、$\Theta(n)$ と $\Theta(\log n)$ という質的な差になって現れるはずです。実装自体はどちらも十数行で、コードの見た目からは速さの差が想像しにくいところが面白い点です。

続いてソートを2つ。

def bubble_sort(a):
    """バブルソート: 隣接交換を繰り返す Θ(n^2)"""
    a = list(a)
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:      # 交換が起きなければ既にソート済み
            break
    return a


def insertion_sort(a):
    """挿入ソート: Θ(n^2) だが定数倍が小さい"""
    a = list(a)
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a


def merge_sort(a):
    """マージソート: 分割統治 Θ(n log n)"""
    if len(a) <= 1:
        return list(a)
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])
    out.extend(right[j:])
    return out

バブルソートと挿入ソートはどちらも $\Theta(n^2)$ ですが、内側ループでやっていることが違います。バブルソートは条件が真になるたびにタプル交換を行い、挿入ソートは単純な代入でずらすだけです。同じオーダーでも定数倍が違うという後半の実験に、この2つを使います。

計測ハーネス

時間計測は思いのほか繊細です。OSのスケジューリングやガベージコレクションで、たまたま遅い測定値が混ざります。そこで「同じ処理を複数回まわした合計時間」を取り、さらにそれを何試行か繰り返して最小値を採用します。平均ではなく最小を取るのは、外乱は必ず時間を「増やす」方向にしか働かないので、最小値が最も真の値に近いからです。

def best_time(func, reps, trials=3):
    """func を reps 回実行した時間の最小値を reps で割って返す"""
    best = float("inf")
    for _ in range(trials):
        t0 = time.perf_counter()
        for _ in range(reps):
            func()
        best = min(best, time.perf_counter() - t0)
    return best / reps


def loglog_slope(ns, ts):
    """両対数プロットの傾き（= 多項式の次数の推定値）"""
    x = np.log(np.asarray(ns, dtype=float))
    y = np.log(np.asarray(ts, dtype=float))
    return np.polyfit(x, y, 1)[0]

loglog_slope が今回の主役です。$\log T$ と $\log n$ に1次式を当てはめ、その傾きを返します。$\Theta(n)$ なら1、$\Theta(n^2)$ なら2、$\Theta(\log n)$ なら（多項式ではないので）ほぼ0が出るはずです。

探索の計測 — O(n) と O(log n) を見分ける

線形探索は最悪ケース（末尾の要素を探す）で測ります。二分探索は1回が速すぎて計測の分解能を下回るので、100件のランダムな問い合わせをまとめて実行し、ループ自体のオーバーヘッドを差し引いてから1件あたりに直します。

ns_search = [2 ** k for k in range(8, 21)]      # 256 〜 1,048,576
t_linear, t_binary = [], []

for n in ns_search:
    arr = list(range(n))
    # 線形探索（最悪ケース: 末尾を探す）
    reps = max(3, int(2e6 // n))
    t_linear.append(best_time(lambda: linear_search(arr, n - 1), reps))
    # 二分探索（100件のランダム問い合わせ、ループ分を差し引く）
    queries = [random.randrange(n) for _ in range(100)]
    t_all = best_time(lambda: [binary_search(arr, q) for q in queries], 200, 5)
    t_ovh = best_time(lambda: [None for q in queries], 200, 5)
    t_binary.append((t_all - t_ovh) / 100)

print(f"線形探索 両対数傾き : {loglog_slope(ns_search, t_linear):.3f}")
print(f"二分探索 両対数傾き : {loglog_slope(ns_search, t_binary):.3f}")

# 二分探索は log n に対して線形か？
x = np.log2(np.asarray(ns_search, dtype=float))
coef = np.polyfit(x, np.asarray(t_binary), 1)
r2 = np.corrcoef(x, np.asarray(t_binary))[0, 1] ** 2
print(f"二分探索 t = {coef[0]*1e6:.4f}us * log2(n) + {coef[1]*1e6:.4f}us,  R^2 = {r2:.4f}")
print(f"n を {ns_search[-1]//ns_search[0]} 倍にしたとき, "
      f"線形は {t_linear[-1]/t_linear[0]:.0f} 倍, 二分は {t_binary[-1]/t_binary[0]:.2f} 倍")

手元のMacBookでの実行例は次のようになりました（数値は環境依存です）。

線形探索 両対数傾き : 1.005
二分探索 両対数傾き : 0.113
二分探索 t = 0.0674us * log2(n) + -0.0460us,  R^2 = 0.9793
n を 4096 倍にしたとき, 線形は 5200 倍, 二分は 2.94 倍

この4行に、この記事の主張がほぼ全部詰まっています。線形探索の両対数傾きは1.005で、理論値1にきわめて近い——実測から $\Theta(n)$ が読み取れました。一方二分探索の傾きは0.113で、ほぼ0です。傾き0は「$n$ を何倍にしても時間が変わらない」という意味であり、対数関数が多項式的にはほとんど増えないことを反映しています。実際、$n$ を4096倍にしたとき、線形探索は5200倍も遅くなったのに、二分探索はたった2.94倍しか遅くなりませんでした。理論上は $\log_2(2^{20})/\log_2(2^8) = 20/8 = 2.5$ 倍のはずで、計測ノイズと関数呼び出しのオーバーヘッドを考えれば妥当な一致です。

さらに、二分探索の時間を $\log_2 n$ の1次関数で当てはめると決定係数 $R^2 = 0.979$ が得られ、1レベル下るごとに約0.067マイクロ秒という係数が出ました。「時間が $\log n$ に比例する」ことが、実測データから直接確認できたことになります。

なお、実測の傾きが1ちょうどにならず、測定を繰り返すと1.00〜1.05のあたりで揺れるのは、$n$ が大きくなると配列がキャッシュに載らなくなり、1要素あたりのアクセスコストがじわりと増えるためです。理論モデルは「メモリアクセスは一律 $O(1)$」を仮定しますが、実機には階層があります。オーダーは実機の挙動をかなりよく予測しますが、完璧ではないことも押さえておきましょう。

ソートの計測 — Θ(n²) と Θ(n log n) を見分ける

次はソートです。$n$ を32から2048まで倍々に変えて測ります。

ns_sort = [2 ** k for k in range(5, 12)]        # 32 〜 2048
t_bubble, t_insertion, t_merge = [], [], []

for n in ns_sort:
    data = [random.random() for _ in range(n)]
    reps = max(3, int(3e5 // (n * math.log2(n))))
    t_bubble.append(best_time(lambda: bubble_sort(data), max(2, reps // 4)))
    t_insertion.append(best_time(lambda: insertion_sort(data), max(2, reps // 4)))
    t_merge.append(best_time(lambda: merge_sort(data), reps))

print(f"バブルソート 両対数傾き : {loglog_slope(ns_sort, t_bubble):.3f}")
print(f"挿入ソート   両対数傾き : {loglog_slope(ns_sort, t_insertion):.3f}")
print(f"マージソート 両対数傾き : {loglog_slope(ns_sort, t_merge):.3f}")

for n, b, m in zip(ns_sort, t_bubble, t_merge):
    print(f"n={n:>5}  バブル={b*1e3:9.4f}ms  マージ={m*1e3:8.4f}ms  比={b/m:6.2f}")

実行例です。

バブルソート 両対数傾き : 2.029
挿入ソート   両対数傾き : 2.015
マージソート 両対数傾き : 1.120
n=   32  バブル=   0.0237ms  マージ=  0.0218ms  比=  1.09
n=   64  バブル=   0.0890ms  マージ=  0.0491ms  比=  1.81
n=  128  バブル=   0.3684ms  マージ=  0.1034ms  比=  3.56
n=  256  バブル=   1.4350ms  マージ=  0.2273ms  比=  6.31
n=  512  バブル=   6.1475ms  マージ=  0.4983ms  比= 12.34
n= 1024  バブル=  26.3663ms  マージ=  1.1099ms  比= 23.76
n= 2048  バブル= 105.1845ms  マージ=  2.2631ms  比= 46.48

まず傾きに注目してください。バブルソートは2.029、挿入ソートは2.015で、いずれも理論値2にぴったりです。両方とも $\Theta(n^2)$ であることが、実測から独立に確認できました。

そしてマージソートの傾きは1.120。ここが微妙で面白いところです。$\Theta(n \log n)$ は多項式ではないので、両対数プロットは厳密には直線になりません。それでも局所的な傾きは計算できて、$T = n \log_2 n$ の両対数の傾きは

$$ \frac{d \log T}{d \log n} = \frac{d}{d \log n}\left(\log n + \log \log_2 n\right) = 1 + \frac{1}{\ln n} $$

となります。測定範囲 $n \in [32, 2048]$ の幾何平均は $\sqrt{32 \times 2048} = 256$ で、$\ln 256 = 5.545$ ですから、理論的な傾きの予測値は $1 + 1/5.545 = 1.180$。実測の1.120はこの予測の近くにあり、少なくとも「1より少し大きく、2よりはるかに小さい」という位置づけははっきりしています（計測を繰り返すと1.09〜1.18の範囲でばらつきます）。「$n \log n$ は $n$ より少しだけ傾きが急」という微妙な違いを、実測から拾えたことになります。

最後の列の比も雄弁です。$n = 32$ ではバブルとマージの実行時間はほぼ同じ（比1.09）なのに、$n$ を64倍の2048にすると46.5倍もの差がつきました。$n$ を2倍にするごとに比が約2倍ずつ開いていくのは、$n^2 / (n \log n) = n / \log n$ が $n$ にほぼ比例して増えるからです。

理論曲線との重ね合わせ

傾きだけでなく、曲線の形そのものが理論と合うかを確かめましょう。実測値に $C n^2$ と $C’ n \log_2 n$ をフィットして重ねます。

fig, axes = plt.subplots(1, 2, figsize=(13, 5))

# 左: ソートの実測と理論曲線
ax = axes[0]
ns = np.asarray(ns_sort, dtype=float)
ax.loglog(ns, np.array(t_bubble) * 1e3, "o-", color="crimson", label="バブルソート（実測）")
ax.loglog(ns, np.array(t_merge) * 1e3, "s-", color="royalblue", label="マージソート（実測）")
c_bub = np.mean(np.array(t_bubble) / ns ** 2)                 # n^2 の係数
c_mer = np.mean(np.array(t_merge) / (ns * np.log2(ns)))        # n log n の係数
ax.loglog(ns, c_bub * ns ** 2 * 1e3, "--", color="crimson", alpha=0.6,
          label=r"理論 $C n^2$")
ax.loglog(ns, c_mer * ns * np.log2(ns) * 1e3, "--", color="royalblue", alpha=0.6,
          label=r"理論 $C\, n \log_2 n$")
ax.set_xlabel("データ数 $n$"); ax.set_ylabel("実行時間 [ms]")
ax.set_title("ソートの実行時間と理論曲線（両対数）")
ax.legend(); ax.grid(True, which="both", alpha=0.3)

# 右: 探索の実測
ax = axes[1]
nss = np.asarray(ns_search, dtype=float)
ax.loglog(nss, np.array(t_linear) * 1e6, "o-", color="darkorange", label="線形探索（実測）")
ax.loglog(nss, np.array(t_binary) * 1e6, "s-", color="seagreen", label="二分探索（実測）")
c_lin = np.mean(np.array(t_linear) / nss)
ax.loglog(nss, c_lin * nss * 1e6, "--", color="darkorange", alpha=0.6, label=r"理論 $C n$")
ax.set_xlabel("データ数 $n$"); ax.set_ylabel("1回あたりの時間 [μs]")
ax.set_title("探索の実行時間（両対数）: 傾き1 と 傾き≈0")
ax.legend(); ax.grid(True, which="both", alpha=0.3)

plt.tight_layout()
plt.show()

ソートと探索の実測時間を両対数で描き理論曲線を重ねた2枚組の図。左はバブルソートが傾き2.03でCn^2に、マージソートが傾き1.12でCn log2 nに乗ることを示し、右は線形探索が傾き1.00の直線、二分探索が傾き0.11でほぼ水平になることを示す

左のグラフでは、バブルソートの実測点（丸）が破線の $Cn^2$ にほぼ乗り、マージソートの実測点（四角）が $C n \log_2 n$ に乗ります。両対数上でバブルの直線が急で、マージが緩やかなのが一目瞭然です。右のグラフでは、線形探索が傾き1のきれいな直線を描くのに対し、二分探索はほぼ水平で、$n$ を256から100万まで4096倍に増やしても縦方向にはわずかしか動きません。両対数プロットで「傾き」を見るという操作が、まさに定数倍を捨ててオーダーだけを抽出する行為であることが、視覚的にも納得できます。

なお、フィットの良さを数値でも確かめると、バブルソートを $C n^2 + D$ で最小二乗フィットしたときの決定係数は $R^2 = 0.99998$、マージソートを $C n \log_2 n + D$ でフィットすると $R^2 = 0.9989$ でした。計測を繰り返してもどちらも $R^2 > 0.998$ に収まり、理論モデルが実測をほぼ完全に説明しています。

定数倍の逆転 — 小さい n ではオーダーが悪いほうが速い

$O$ 記法は「$n$ が十分大きいとき」の話でした。逆に言えば、$n$ が小さければオーダーの悪いアルゴリズムが勝つことがあるはずです。これを実際に見てみましょう。挿入ソート（$\Theta(n^2)$、定数倍が小さい）とマージソート（$\Theta(n \log n)$、再帰呼び出しとリスト生成のオーバーヘッドが大きい）を、小さい $n$ で比べます。

print(f"{'n':>5} {'挿入[us]':>12} {'マージ[us]':>12} {'比':>8}  勝者")
for n in [4, 8, 16, 24, 32, 48, 64, 96, 128, 192, 256]:
    data = [random.random() for _ in range(n)]
    reps = max(50, int(2e5 // (n * max(1.0, math.log2(n)))))
    t_ins = best_time(lambda: insertion_sort(data), reps, 5)
    t_mer = best_time(lambda: merge_sort(data), reps, 5)
    winner = "挿入ソート" if t_ins < t_mer else "マージソート"
    print(f"{n:>5} {t_ins*1e6:>12.3f} {t_mer*1e6:>12.3f} {t_ins/t_mer:>8.3f}  {winner}")

実行例です。

    n     挿入[us]   マージ[us]       比  勝者
    4        0.432        1.419    0.305  挿入ソート
    8        1.060        3.695    0.287  挿入ソート
   16        3.069        8.409    0.365  挿入ソート
   24        5.930       13.981    0.424  挿入ソート
   32       11.944       21.176    0.564  挿入ソート
   48       25.015       31.757    0.788  挿入ソート
   64       44.865       45.994    0.975  挿入ソート
   96      106.130       73.687    1.440  マージソート
  128      183.158       99.785    1.836  マージソート
  192      327.529      162.207    2.019  マージソート
  256      632.798      228.180    2.773  マージソート

挿入ソートとマージソートを小さいnで比較した2枚組の図。左は実行時間の折れ線でn≈66で交差すること、右は時間比が1を横切る点が閾値n0であることを示す

はっきりと逆転が観測できました。左のグラフでは、$n$ が小さいうちは赤い挿入ソートの折れ線が青いマージソートより下にありますが、$n = 64$ 付近で両者が接触し、そこから先は赤が一気に上へ離れていきます。右のグラフはこれを時間比で描いたもので、比が1を横切る点——この実行では $n \approx 66$——が、まさに $O$ 記法の閾値 $n_0$ の正体です。

数値でも確認しておきます。$n \le 64$ では $\Theta(n^2)$ の挿入ソートのほうが速く、$n = 4$ では実に3倍以上の差をつけています。ところが $n = 96$ では立場が入れ替わり、$n = 256$ ではマージソートが2.8倍速い。交差点の正確な位置はマシンやその時の負荷で数十のオーダーで揺れますが（筆者の環境では50〜90の範囲で変動しました）、「小さい $n$ では挿入ソートが勝ち、ある閾値を超えるとマージソートが勝つ」という構図は常に再現します。

この逆転は $O$ 記法の反例ではなく、むしろ定義そのものです。$O$ の定義には $n_0$ という閾値がありました。「$n_0$ 以降で成り立てばよい」という条件は、裏を返せば「$n_0$ より小さいところでは何が起きても知らない」と言っているのです。今回の実験では、その $n_0$ が具体的に数十という数字として姿を現したことになります。

この事実は実務で積極的に利用されています。PythonやJavaの標準ソートに使われるTimsortは、配列を小さな塊（run）に分けたあと、長さがおよそ32〜64未満の塊に対しては挿入ソートを使い、それ以上でマージを行うハイブリッド構造です。C++の std::sort（イントロソート）も、部分区間が小さくなったら挿入ソートに切り替えます。「漸近的に最良のアルゴリズム」と「実用上最速のアルゴリズム」は別物であり、後者はたいてい前者と定数倍の小さいアルゴリズムの組み合わせになります。オーダーは設計の出発点であって、終着点ではありません。

償却計算量の実測

最後に、動的配列の償却 $O(1)$ を実測で確かめます。まずCPythonのリストの容量がどう増えるかを覗いてみましょう。sys.getsizeof の差分から、確保されている要素数（容量）が推定できます。

import sys

capacities, prev = [], -1
lst = []
for i in range(200000):
    lst.append(i)
    cap = (sys.getsizeof(lst) - sys.getsizeof([])) // 8   # ポインタ8バイト
    if cap != prev:
        capacities.append((i + 1, cap))
        prev = cap

print("容量が増えた瞬間(要素数, 容量) 先頭10件:", capacities[:10])
print("再確保が起きた回数:", len(capacities))
ratios = [capacities[k + 1][1] / capacities[k][1] for k in range(len(capacities) - 6, len(capacities) - 1)]
print("後半の容量比 c[k+1]/c[k]:", [round(r, 4) for r in ratios])

実行例です。

容量が増えた瞬間(要素数, 容量) 先頭10件: [(1, 4), (5, 8), (9, 16), (17, 24), (25, 32), (33, 40), (41, 52), (53, 64), (65, 76), (77, 92)]
再確保が起きた回数: 72
後半の容量比 c[k+1]/c[k]: [1.125, 1.125, 1.125, 1.125, 1.125]

容量比が正確に1.125——先に述べたCPythonの newsize + (newsize >> 3) + 6 という成長式が実測で確認できました。教科書の「倍々（$r=2$）」ではなく $r = 1.125$ ですが、$r > 1$ である限り償却 $O(1)$ は成り立ちます。注目すべきは20万要素を追加する間に再確保がわずか72回しか起きていない点です。要素数に比例して増えるのではなく、対数的にしか増えていません。$\log_{1.125} 200000 \approx 104$ 回が上限の目安で、序盤は +6 の効果で成長が速いぶん、実測は72回に収まっています。

次に、実際の時間を測ります。

print(f"{'n':>10} {'総時間[ms]':>12} {'1回あたり[ns]':>15}")
for n in [10 ** 4, 10 ** 5, 10 ** 6, 10 ** 7]:
    t0 = time.perf_counter()
    lst = []
    for i in range(n):
        lst.append(i)
    dt = time.perf_counter() - t0
    print(f"{n:>10} {dt*1e3:>12.3f} {dt/n*1e9:>15.2f}")


def total_copies(n, mode, inc=100):
    """n 回の push_back で発生するコピー要素の総数を数える"""
    cap, size, copies = 1, 0, 0
    for _ in range(n):
        if size == cap:
            copies += size
            cap = cap * 2 if mode == "double" else cap + inc
        size += 1
    return copies


print(f"\n{'n':>8} {'倍々のコピー総数':>18} {'+100ずつのコピー総数':>22}")
for n in [1000, 10000, 100000]:
    d, c = total_copies(n, "double"), total_copies(n, "const")
    print(f"{n:>8} {d:>12} ({d/n:.2f}n) {c:>14} ({c/n:.1f}n)")

実行例です。

         n      総時間[ms]       1回あたり[ns]
     10000        0.678           67.80
    100000        2.663           26.63
   1000000       28.961           28.96
  10000000      305.401           30.54

       n   倍々のコピー総数   +100ずつのコピー総数
    1000         1023 (1.02n)           4510 (4.5n)
   10000        16383 (1.64n)         495100 (49.5n)
  100000       131071 (1.31n)       49951000 (499.5n)

上半分が決定的です。$n$ を $10^4$ から $10^7$ まで1000倍に振ったのに、append 1回あたりの時間は30ナノ秒前後のまま、2倍程度の範囲にしか動いていません。もし append が本当に $O(n)$ なら、1回あたりの時間も1000倍違わなければおかしい。実際にはほぼ横ばいなので、償却 $O(1)$ が実測で裏付けられました。$n = 10^4$ だけ68ナノ秒とやや高いのは、測定時間そのものが1ミリ秒に満たず、タイマーの分解能とループ立ち上がりのオーバーヘッドが相対的に効いてしまうためで、オーダーの違いではありません。

下半分は、倍々拡張と定数増分拡張の決定的な差を数えたものです。倍々拡張のコピー総数は $n = 1000$ で $1.02n$、$n = 10^5$ で $1.31n$ と、どの $n$ でも$2n$ を超えません。これは集約法で証明した $\sum 2^k < 2n$ という不等式そのものです（値が $1.02n \sim 1.64n$ の間で振動するのは、$n$ が2のべき乗の直後か直前かで最後の再確保のタイミングが変わるためで、上界 $2n$ は常に守られています）。

一方、100要素ずつ増やす方式では、$n = 1000$ で $4.5n$、$n = 10^4$ で $49.5n$、$n = 10^5$ で $499.5n$ と、係数そのものが $n$ に比例して増えています。これは総コストが $\Theta(n^2)$、1回あたりが $\Theta(n)$ であることの直接的な証拠です。理論式 $n^2/(2\delta) = 10^{10}/200 = 5 \times 10^7$ に対して実測が $4.995 \times 10^7$ ですから、導出した式がそのまま当たっています。「容量を定数ずつ増やす」という一見穏当な実装が、$n = 10^5$ の時点で倍々の380倍ものコピーを発生させる——償却計算量を知らないと踏んでしまう地雷です。

まとめ

本記事では、計算量オーダー（$O$ 記法）を定義から実測まで通して解説しました。

  • 定義: $f(n) = O(g(n))$ とは、「ある定数 $c > 0$ と閾値 $n_0$ が存在して、$n \ge n_0$ で $f(n) \le c\,g(n)$」ということ。$c$ が自由に選べるので定数倍が、$n_0$ 以降だけ見ればよいので低次項が、それぞれ自動的に無視される。上界が $O$、下界が $\Omega$、両方が揃えば $\Theta$。
  • 落とせる理由: 多項式なら $n \ge 1$ で $n^k \le n^d$ を使い、係数の絶対値の総和を $c$ に取れば $O(n^d)$ が示せる。定数倍は $c$ に吸収され、対数の底も変換公式が定数倍なので消える。
  • 数え方: 逐次実行は和の法則で最大のブロックが支配、入れ子は積の法則で掛け算。ただし内側の回数が変数に依存するときは和として厳密に数える（三角ループは $n(n-1)/2 = \Theta(n^2)$、調和級数型は $\Theta(n \log n)$）。変数が乗除算で更新されるループは $\Theta(\log n)$。
  • マスター定理: $T(n) = aT(n/b) + f(n)$ は、再帰木の各階層のコストが公比 $a/b^c$ の等比級数になる。公比が1より大きければ葉が支配して $\Theta(n^{\log_b a})$（ケース1）、1なら全階層が等しく $\Theta(n^{\log_b a} \log n)$（ケース2）、1未満なら根が支配して $\Theta(f(n))$（ケース3）。マージソートはケース2で $\Theta(n \log n)$、二分探索もケース2で $\Theta(\log n)$、シュトラッセン法はケース1で $\Theta(n^{\log_2 7})$。
  • 償却計算量: 動的配列の倍々拡張では、コピーの総量が $\sum_{k} 2^k < 2n$ に収まるので総コストが $3n$ 未満、償却 $O(1)$。ポテンシャル関数 $\Phi = 2s - m$ を使うと、どちらの場合も償却コストがぴったり3になることが機械的に示せる。定数ずつ増やす実装だと総コストが $\Theta(n^2)$ になり、成長率が定比であることが本質的。
  • 実測: 両対数プロットの傾きは、線形探索1.005、バブルソート2.029、挿入ソート2.015、マージソート1.120。マージソートの1.120は理論予測 $1 + 1/\ln n \approx 1.18$ の近傍にあり、$\Theta(n \log n)$ が $\Theta(n)$ よりわずかに急であることまで捉えられた。二分探索は傾き0.113とほぼ水平で、$\log_2 n$ に対する線形フィットが $R^2 = 0.98$。
  • $n_0$ の実在: 挿入ソートは60〜70要素あたりまでマージソートより速く、そこを超えると逆転する。$O$ 記法の $n_0$ は抽象的な記号ではなく、実測で見える具体的な数字である。Timsortやイントロソートが「小さい区間は挿入ソート」というハイブリッド構造を取るのは、この事実を利用しているから。

計算量オーダーは、アルゴリズムを設計するときの「地図」です。$n$ がどこまで大きくなるかを見積もり、それに耐えるオーダーを選ぶ。$n = 10^6$ を扱うなら $O(n \log n)$ までが実用圏で、$O(n^2)$ は諦めるか近似に逃げる——この判断が瞬時にできるようになると、実装を始める前に設計の可否が読めるようになります。一方で、オーダーが同じなら定数倍とキャッシュ効率の勝負になり、そこからは実測が主役になります。理論で候補を絞り、実測で決める——この二段構えが、性能を扱う正しい態度です。

次のステップとして、以下の記事も参考にしてください。

関連記事

前の記事

IEEE754浮動小数点数と数値誤差 — 0.1+0.2が0.3にならない理由

次の記事

ボード線図の描き方と読み方を完全解説

関連タグ: O記法 アルゴリズム データ構造 計算量