# 計算量と漸化式｜オーダー記法・マスター定理・漸化式の解き方

> O・Ω・Θ記法の定義と極限による判定、分割統治の漸化式を解くマスター定理の3つの場合と適用条件、置換法・再帰木による厳密解の計算例、答案でよくある誤りを数式で解説します。

- HTML版（正規URL）: https://inshihub.com/basics/algorithms/complexity-recurrences
- 科目: [アルゴリズムとデータ構造](https://inshihub.com/basics/algorithms)（大学基礎課程の数学・物理・化学・生物・情報）
- 最終更新: 2026-11-16

アルゴリズムの計算量は、入力の大きさ $n$ に対する基本操作の回数を関数 $T(n)$ で表し、その増え方を $O$・$\Omega$・$\Theta$ 記法で比べる。分割統治法の計算量は $T(n) = aT(n/b) + f(n)$ の形の漸化式になり、$f(n)$ と $n^{\log_b a}$ の大小を比べるマスター定理で多くの場合の解が決まる。マスター定理の当てはまらない漸化式は、展開して和を計算する再帰木か、解を予想して帰納法で示す置換法で解く。

## 計算量とオーダー記法の定義

### 定義：時間計算量

大きさ $n$ の入力に対してアルゴリズムが行う基本操作（比較、代入、算術演算など）の回数を時間計算量という。大きさ $n$ の入力全体での最大値を最悪時の計算量、入力の分布を決めたときの期待値を平均時の計算量と呼ぶ。使う記憶領域の量を同じように数えたものを領域計算量という。

### 定義：$O$・$\Omega$・$\Theta$ 記法

$f, g$ を十分大きな $n$ で正の値をとる関数とする。

$$\begin{aligned} f(n) = O(g(n)) &\iff \exists c > 0,\ \exists n_0,\ \forall n \ge n_0:\ f(n) \le c\, g(n) \\ f(n) = \Omega(g(n)) &\iff \exists c > 0,\ \exists n_0,\ \forall n \ge n_0:\ f(n) \ge c\, g(n) \\ f(n) = \Theta(g(n)) &\iff f(n) = O(g(n)) \text{ かつ } f(n) = \Omega(g(n)) \end{aligned}$$

$O$ は上界、$\Omega$ は下界、$\Theta$ は上下両方からの評価を表す。$f(n) = o(g(n))$ は「任意の $c > 0$ に対して、十分大きな $n$ で $f(n) < c\,g(n)$」を意味する。

### 定理・法則：極限による判定

条件：

$f, g$ は十分大きな $n$ で正。極限 $L = \lim_{n \to \infty} f(n)/g(n)$ が存在する（$\infty$ を含む）。

主張：

- $0 < L < \infty$ なら $f(n) = \Theta(g(n))$。
- $L = 0$ なら $f(n) = o(g(n))$、特に $f(n) = O(g(n))$。
- $L = \infty$ なら $f(n) = \Omega(g(n))$ で、$f(n) = O(g(n))$ ではない。

要点：

極限が存在しない場合はこの判定は使えず、定義に戻る。たとえば $f(n) = n(2 + \sin n)$ と $g(n) = n$ では比が振動するが、$n \le f(n) \le 3n$ から $f(n) = \Theta(n)$ である。

### 計算例：定義どおりに $\Theta$ を示す

$f(n) = 3n^2 + 5n$ が $\Theta(n^2)$ であることを、定数 $c, n_0$ を具体的に与えて示せ。

解答：

$n \ge 1$ のとき $5n \le 5n^2$ なので $f(n) \le 8n^2$。また $f(n) \ge 3n^2$。よって $c_1 = 3$、$c_2 = 8$、$n_0 = 1$ として $3n^2 \le f(n) \le 8n^2$（$n \ge 1$）が成り立ち、$f(n) = \Theta(n^2)$。

検算：

極限でも $\lim_{n\to\infty} (3n^2 + 5n)/n^2 = 3$ で、$0 < 3 < \infty$ から同じ結論になる。

## マスター定理と使える条件

### 定理・法則：マスター定理

条件：

$a \ge 1$、$b > 1$ は定数、$f(n)$ は十分大きな $n$ で正の関数で、$T(n) = aT(n/b) + f(n)$（$n/b$ は $\lfloor n/b \rfloor$ や $\lceil n/b \rceil$ でもよい）。$\alpha = \log_b a$ とおく。

主張：

1. ある $\varepsilon > 0$ で $f(n) = O(n^{\alpha - \varepsilon})$ なら $T(n) = \Theta(n^{\alpha})$。
2. $f(n) = \Theta(n^{\alpha})$ なら $T(n) = \Theta(n^{\alpha} \log n)$。
3. ある $\varepsilon > 0$ で $f(n) = \Omega(n^{\alpha + \varepsilon})$ であり、さらにある定数 $c < 1$ と十分大きな $n$ で $a f(n/b) \le c f(n)$（正則条件）が成り立つなら $T(n) = \Theta(f(n))$。

要点：

再帰木の深さ $j$ の段の和は $a^j f(n/b^j)$ で、葉は $a^{\log_b n} = n^{\alpha}$ 個ある。場合1は葉の和、場合3は根の項が全体を決め、場合2は $\log_b n$ 段がほぼ同じ大きさになる。$f(n)$ が $n^{\alpha}$ より大きく（小さく）ても多項式の差 $n^{\varepsilon}$ がなければ、3つのどれにも当てはまらない。

場合2は $f(n) = \Theta(n^{\alpha} \log^k n)$（$k \ge 0$）に広げられ、そのとき $T(n) = \Theta(n^{\alpha} \log^{k+1} n)$ となる。この拡張版を使う答案では、拡張版であることを書いておく。$T(n) = T(n-1) + f(n)$ のように引数が定数ずつしか減らない漸化式は、$b > 1$ の形でないのでマスター定理の対象外である。

## よく出る漸化式の解

### 代表的な漸化式（$T(1)$ は定数）

- 二分探索

  $$T(n) = T(n/2) + \Theta(1) \ \Rightarrow\ T(n) = \Theta(\log n)$$

  マスター定理の場合2（$a = 1$、$b = 2$、$\alpha = 0$）。

- マージソート

  $$T(n) = 2T(n/2) + \Theta(n) \ \Rightarrow\ T(n) = \Theta(n \log n)$$

  場合2（$\alpha = 1$）。

- 木の走査

  $$T(n) = 2T(n/2) + \Theta(1) \ \Rightarrow\ T(n) = \Theta(n)$$

  場合1（$\alpha = 1$、$f(n) = O(n^{1 - \varepsilon})$）。

- カラツバ法

  $$T(n) = 3T(n/2) + \Theta(n) \ \Rightarrow\ T(n) = \Theta(n^{\log_2 3})$$

  $\log_2 3 \approx 1.585$。場合1。

- 挿入ソートの最悪

  $$T(n) = T(n-1) + \Theta(n) \ \Rightarrow\ T(n) = \Theta(n^2)$$

  和 $\sum_{k=1}^{n} k = n(n+1)/2$ から。

- 素朴なフィボナッチ

  $$T(n) = T(n-1) + T(n-2) + \Theta(1) \ \Rightarrow\ T(n) = \Theta(\varphi^n), \quad \varphi = \frac{1 + \sqrt{5}}{2}$$

  特性方程式 $x^2 = x + 1$ の大きいほうの解が増え方を決める。

### 増え方の順序

- 代表的な関数

  $$1 \prec \log n \prec \sqrt{n} \prec n \prec n \log n \prec n^2 \prec n^3 \prec 2^n \prec n! \prec n^n$$

  $f \prec g$ は $f = o(g)$ の意味。任意の $k > 0$、$\varepsilon > 0$ で $\log^k n = o(n^{\varepsilon})$、$n^k = o(2^n)$。

- スターリングの公式から

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

## 再帰木と置換法で漸化式を解く

再帰木の方法は次の順で進める。

1. 漸化式を1段ずつ展開し、深さ $j$ の段にある部分問題の数と大きさを書く（例：$a^j$ 個、大きさ $n/b^j$）。
2. 段ごとの和 $a^j f(n/b^j)$ を求める。
3. 深さ $\log_b n$ まで足し、葉の分 $\Theta(n^{\log_b a})$ を加える。
4. 得た式を予想として、必要なら帰納法（置換法）で上界・下界を示す。

### 計算例：$2T(n/2) + n$ の厳密解

$n = 2^k$ に対して $T(1) = 0$、$T(n) = 2T(n/2) + n$ を解け。

解答：

両辺を $n$ で割って $S(k) = T(2^k)/2^k$ とおくと $S(k) = S(k-1) + 1$、$S(0) = 0$ なので $S(k) = k$。よって

$$T(n) = n \log_2 n$$

再帰木で見ると、各段の和はどれも $n$ で、段の数は $\log_2 n$ である。

検算：

$T(2) = 2$、$T(4) = 2 \cdot 2 + 4 = 8$、$T(8) = 2 \cdot 8 + 8 = 24$ で、$n \log_2 n$ はそれぞれ $2, 8, 24$。マスター定理の場合2の $\Theta(n \log n)$ とも一致する。

### 計算例：$3T(n/2) + n$ の厳密解

$n = 2^k$ に対して $T(1) = 1$、$T(n) = 3T(n/2) + n$ を解け。

解答：

展開すると深さ $j$ の段の和は $3^j \cdot n/2^j = n(3/2)^j$ で、深さ $k$ に $3^k$ 個の葉がある。

$$T(n) = \sum_{j=0}^{k-1} n\left(\frac{3}{2}\right)^j + 3^k = 2n\left(\left(\frac{3}{2}\right)^k - 1\right) + 3^k = 3 \cdot 3^k - 2n$$

$3^k = 3^{\log_2 n} = n^{\log_2 3}$ なので $T(n) = 3n^{\log_2 3} - 2n = \Theta(n^{\log_2 3})$。

検算：

$T(2) = 3 + 2 = 5$ と $3 \cdot 3 - 4 = 5$、$T(4) = 15 + 4 = 19$ と $3 \cdot 9 - 8 = 19$ が一致する。$f(n) = n = O(n^{\log_2 3 - 0.5})$ なのでマスター定理の場合1とも合う。

### 計算例：マスター定理の基本形で解けない漸化式

$n = 2^k$ に対して $T(1) = 0$、$T(n) = 2T(n/2) + n\log_2 n$ を解け。

解答：

$\alpha = 1$ で、$f(n)/n^{\alpha} = \log_2 n$ は増えるが、どの $\varepsilon > 0$ でも $n^{\varepsilon}$ より遅い。よって場合3は使えない。再帰木では深さ $j$ の段の和が $2^j \cdot (n/2^j)\log_2(n/2^j) = n(k - j)$ なので

$$T(n) = \sum_{j=0}^{k-1} n(k-j) = n\,\frac{k(k+1)}{2} = \frac{n \log_2 n\,(\log_2 n + 1)}{2} = \Theta(n \log^2 n)$$

検算：

$T(2) = 2$、$T(4) = 2 \cdot 2 + 4 \cdot 2 = 12$ で、式の値は $2 \cdot 1 \cdot 2/2 = 2$、$4 \cdot 2 \cdot 3/2 = 12$。拡張版の場合2（$k = 1$）の $\Theta(n\log^2 n)$ とも一致する。

## 答案でよくある誤り

1. $O$ を「ちょうどその増え方」の意味で使う。$n = O(n^2)$ も正しいので、上下両方を言うときは $\Theta$ を使い、下界も示す。
2. $f(n) = n\log n$、$a = b = 2$ にマスター定理の場合3を当てはめる。$n \log n$ は $n^{1+\varepsilon}$ より遅いので場合3の条件を満たさない。再帰木で解くか、拡張版の場合2を明示して使う。
3. 場合3で正則条件 $af(n/b) \le cf(n)$（$c < 1$）を確かめずに結論する。多項式の $f$ では成り立つが、答案では一行で確認を書く。
4. $T(n) = T(n-1) + n$ にマスター定理を使う。引数が定数ずつ減る漸化式は対象外で、和 $\sum k = \Theta(n^2)$ を直接計算する。
5. 対数の底を気にして $O(\log_2 n)$ と $O(\log_{10} n)$ を区別する。底の変換は定数倍なのでオーダーは同じだが、$2^{\log_2 n} = n$ と $2^{\log_{10} n}$ のように指数に入ると異なる。

## 計算量と漸化式が出た院試の過去問

### [計算量理論](https://inshihub.com/exam-themes/computational-complexity)（10大学・38問）

- [九州工業大学大学院 共通科目（情報基礎） 2026年度 第1問](https://inshihub.com/exam-solutions/kyushu-institute-of-technology/graduate-school-of-computer-science-and-systems-engineering/information-fundamentals/2026#problem-1): プログラミング
- [京都工芸繊維大学大学院 専門科目（情報工学） 2026年度 第3問](https://inshihub.com/exam-solutions/kyoto-institute-of-technology/graduate-school-of-science-and-technology/information-engineering/2026-first#problem-3): プログラミング(2)
- [名古屋大学大学院 数理情報学 2026年度 第6問](https://inshihub.com/exam-solutions/nagoya-university/graduate-school-of-informatics/mathematical-informatics/2026#problem-6): 離散最適化
- [東京大学 創造情報学 専門科目 2026年度 第3問](https://inshihub.com/exam-solutions/tokyo-university/information-science/creative-informatics-specialized/2026#problem-3): 情報システム用語の説明
- [東京都立大学大学院 情報科学域 専門科目 2026年度 第4問](https://inshihub.com/exam-solutions/tokyo-metropolitan-university/graduate-school-of-systems-design/information-science/2026-summer#problem-4): データ構造とアルゴリズム
- [京都大学 通信情報システムコース 2025年度 第8問](https://inshihub.com/exam-solutions/kyoto-university/graduate-school-of-informatics/communications-and-computer-engineering/2025#problem-8): B-4 データ構造と探索

解答まで無料で読める演習問題:

- [東京大学 創造情報学 専門科目 2025年度 第3問](https://inshihub.com/exam-solutions/tokyo-university/information-science/creative-informatics-specialized/2025#problem-3): 情報システム用語の説明
- [大阪大学 専門科目（情報工学） 2024年度 第1問](https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-engineering/2024#problem-1): アルゴリズムとプログラミング(挿入ソート)
- [大阪大学 専門科目（情報数理学） 2024年度 第1問](https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-and-physical-sciences/2024#problem-1): 情報基礎
- [京都大学 社会情報学コース 2023年度 第2問](https://inshihub.com/exam-solutions/kyoto-university/graduate-school-of-informatics/social-informatics/2023#problem-2): 情報学基礎：最小値・最大値探索