分割統治法とマスター定理
再帰アルゴリズムの計算量を、漸化式とマスター定理で一目で見抜けるようになる。Karatsuba や Strassen が素朴な下界を破る仕組みまで原理から腹落ちさせる。
- 1.分割統治は T(n)=aT(n/b)+f(n) という漸化式に落ちる。a=部分問題の個数、b=縮小率、f(n)=分割と統合のコスト。
- 2.マスター定理は f(n) と基準項 n^(log_b a) の大小で3ケースに場合分けし、再帰木を解かずに計算量を即決する。
- 3.Karatsuba(乗算)や Strassen(行列積)は a を減らして指数 log_b a を下げ、素朴な O(n^2)・O(n^3) を漸近的に破る。
分割統治の漸化式という共通言語
分割統治法は、問題を同型の小さな部分問題に分割し、各部分を再帰で統治し、結果を統合する設計です。マージソートや二分探索が典型ですが、重要なのは、これらの計算量がすべて同じ形の漸化式に落ちることです。
T(n) = a · T(n/b) + f(n)
各記号の意味を正確に押さえます。a は1段で生成される部分問題の個数、b は各部分問題の入力サイズが 1/b に縮む割合、f(n) は分割と統合に費やす非再帰のコストです。マージソートなら2つに割って両方を解くので a=2、サイズは半分なので b=2、併合が O(n) なので f(n)=n。二分探索は片側しか見ないので a=1、b=2、f(n)=O(1) です。
なぜこの形が大切か。再帰の計算量を毎回手で展開するのは骨が折れますが、漸化式の3つのパラメータが決まれば、後述のマスター定理がほぼ機械的に答えを出すからです。計算量記法そのものに不安があれば計算量と Big-O 記法を先に確認してください。
再帰木で「コストの正体」を見る
マスター定理の前に、なぜ答えが3パターンに割れるのかを再帰木で直観しておきます。深さ k の段には部分問題が a^k 個あり、各サイズは n / b^k。各段の総コストは a^k · f(n / b^k) です。
段0: 1個, コスト f(n)
段1: a個, コスト a·f(n/b)
段2: a²個, コスト a²·f(n/b²)
…
段L: a^L個, 各サイズ1（葉）。L = log_b n
葉の総数 = a^(log_b n) = n^(log_b a)
ここで現れる n^(log_b a) が基準項で、葉（最小の部分問題）の総数を表します。木全体のコストは「葉のコスト合計」と「根に近い段のコスト f(n)」のどちらが支配するかで決まります。この2つの綱引きの勝敗が、そのまま3ケースになります。
指数 log_b a は「サイズを b 分の1にするたびに問題数が a 倍になる増殖速度」を1本の指数にまとめた量です。a が大きい（分割数が多い）ほど葉が増えて重くなり、b が大きい（速く縮む）ほど浅くなって軽くなる。Karatsuba や Strassen の改良が効くのは、まさにこの指数を直接小さくするからです。
マスター定理の3ケース
T(n) = a·T(n/b) + f(n)（a >= 1, b > 1）に対し、基準項 n^(log_b a) と f(n) を比べて場合分けします。記号 ε は小さな正の定数です。
| ケース | 条件（f と基準項の関係） | 結論 T(n) | 支配側 |
|---|---|---|---|
| 1 | f(n) = O(n^(log_b a − ε)) | Θ(n^(log_b a)) | 葉が支配 |
| 2 | f(n) = Θ(n^(log_b a)) | Θ(n^(log_b a) · log n) | 各段が均等 |
| 3 | f(n) = Ω(n^(log_b a + ε)) かつ正則条件 | Θ(f(n)) | 根が支配 |
ケース1は f(n) が基準項より多項式的に小さい場合。コストは葉に集中し、答えは Θ(n^(log_b a))。ケース2は両者が同オーダーで、全段がほぼ等しく効くため log n 段ぶんの重みが乗って Θ(n^(log_b a) · log n)。ケース3は f(n) が基準項より多項式的に大きく、かつ正則条件 a·f(n/b) <= c·f(n)（ある c が 1 未満）を満たす場合で、根のコストが支配して Θ(f(n)) になります。
マージソートは a=b=2, f(n)=n。基準項は n^(log_2 2)=n で f(n)=Θ(n) だからケース2、Θ(n log n)。二分探索は a=1, b=2, f(n)=Θ(1)、基準項 n^0=1 でケース2、Θ(log n)。T(n)=2T(n/2)+1 なら f が基準項 n より小さくケース1で Θ(n)。3つの数字を抜き出して比較する手順を体に入れておくと試験でも実務でも速い。
この定理は b が定数で部分問題が等サイズ、という前提に依存します。T(n)=T(n−1)+n（サイズが定数しか減らない）、T(n)=T(n/2)+T(n/3)+n（不等分割）、f(n)=n/log n のようにケース1とケース2のすき間に落ちて多項式差がない場合などは適用外です。こうした形はアクラ＝バジ法（Akra–Bazzi）や再帰木の直接展開で評価します。「機械的に当てはめて誤る」事故が一番多いので前提確認は必須です。
下界を破る応用: Karatsuba と Strassen
マスター定理の真価は、アルゴリズムを設計し直して指数 log_b a を下げる指針になる点にあります。鍵は分割数 a の削減です。
Karatsuba 乗算は n 桁同士の整数積です。素朴な筆算は各桁を総当たりで掛けるので O(n^2)。半分ずつに割ると本来は4つの積（a=4, b=2）が要り、n^(log_2 4)=n^2 で改善しません。Karatsuba は代数的工夫で、4つではなく3つの積で復元できることを示しました。
x = x1·B + x0, y = y1·B + y0 （B は基数の半分の桁）
必要な積: z2 = x1·y1
z0 = x0·y0
z1 = (x1+x0)(y1+y0) − z2 − z0 ← 1回の積で中間項を得る
xy = z2·B² + z1·B + z0
積が3つに減るので a=3, b=2、f(n) は加減算で O(n)。基準項 n^(log_2 3) ≈ n^1.585 がケース1で支配し、Θ(n^1.585)。O(n^2) の壁を初めて破った歴史的な例です。
Strassen の行列積も同じ発想です。n×n 行列の素朴な積は O(n^3)。2×2 ブロックに分けると本来8つのブロック積（a=8, b=2, n^(log_2 8)=n^3）が要りますが、Strassen は7つの積で済む組み合わせを発見しました。a=7, b=2 で n^(log_2 7) ≈ n^2.807、ケース1により Θ(n^2.807) です。
| アルゴリズム | 素朴 | a / b | 改良後の指数 | 計算量 |
|---|---|---|---|---|
| Karatsuba 乗算 | O(n²) | 3 / 2 | log_2 3 ≈ 1.585 | Θ(n^1.585) |
| Strassen 行列積 | O(n³) | 7 / 2 | log_2 7 ≈ 2.807 | Θ(n^2.807) |
両者に共通する本質は、「分割の仕方は変えずに、統合の代数を工夫して部分問題の個数 a を減らす」こと。マスター定理を逆向きに読み、log_b a を下げる余地を探すのが、漸近的な高速化の王道なのです。
Strassen は加減算が増え再帰の定数倍が大きいため、小さい行列ではむしろ遅く、実装では一定サイズ以下で素朴法に切り替えます。Karatsuba も桁数が小さいうちは筆算が速い。下界を破るのは「十分大きい n」での漸近的な話で、現実の選択は定数倍とのトレードオフで決まります。これは比較ソートの下界で見た「下界を破らずに定数を削る」議論の鏡像で、計算量理論の利得が実務でどう効くかを測る視点が要ります。
まとめ: 漸化式を読む力
分割統治は T(n)=aT(n/b)+f(n) という共通の言語を持ち、マスター定理はその3つのパラメータから計算量を即決します。さらにこの定理は、a を減らせば指数が下がるという設計の羅針盤にもなる。Karatsuba と Strassen はその指針を体現した古典です。再帰アルゴリズムを見たらまず3つの数字を抜き出す――この習慣が、計算量を曖昧さなく見抜く土台になります。
プログラミング Article
分割統治法とマスター定理を実務で読む
TL;DRは入口です。実際に選ぶ・使う段階では、何を解決するか、何と比較するか、導入後にどこで詰まるかまで見る必要があります。
解決すること
アルゴリズム
比較で見る軸
難易度: advanced / カテゴリ: プログラミング / タグ数: 5
導入後に効く点
マスター定理は f(n) と基準項 n^(log_b a) の大小で3ケースに場合分けし、再帰木を解かずに計算量を即決する。
先に潰すリスク
用語だけ覚えても、設計・実装・運用でどこに効くかを確認しないと判断を誤る。
- 難易度
- advanced
- カテゴリ
- プログラミング
- タグ数
- 5
判断チェックリスト
- 自社の用途が「アルゴリズム / 分割統治」に近いか確認する。
- 強みである「分割統治は T(n)=aT(n/b)+f(n) という漸化式に落ちる。a=部分問題の個数、b=縮小率、f(n)=分割と統合のコスト。」が本当に評価軸になるか確認する。
- 注意点の「用語だけ覚えても、設計・実装・運用でどこに効くかを確認しないと判断を誤る。」を運用で吸収できるか確認する。
- 公開値や仕様値は、対象プラン・対象機種・対象リージョンまで確認する。
- 既存システム、ID、ネットワーク、監視、バックアップとの接続方法を先に洗い出す。
- 小さく試してから、本番移行、権限設計、障害時手順、コスト監視を決める。