- 物理機リージョン/AZ
- ハイパーバイザVM exit で捕まえる
- VMゲストOS
- コンテナnamespace / cgroup
- プロセスアプリ / DB今ここ
第11期では「半分にすると回数は log で済む」ことを見ました。今回はその log を段数として使い、各段でどれだけ仕事をするかを足し合わせます。
まず結論
分割統治の計算量は「再帰の木を段ごとに見て、各段の仕事を足す」と読めます。段数は、半分ずつにするなら log₂ n です。
各段の仕事が同じならマージソートの n log n になり、下の段ほど仕事が増えるなら葉の数が支配します。数を上と下の半分の桁に分け、半分の桁の掛け算を4回から3回に減らす Karatsuba の方法では、葉の数が n の log₂3 乗(約 n^1.585)です。「再帰だから n log n」とは決まりません。
64桁どうしの掛け算を「半分の桁に分け、半分の桁の掛け算3回に直す」ことを1桁になるまで繰り返します。1桁どうしの掛け算は全部で何回になるでしょうか(筆算なら 64×64 = 4,096 回です)。
当てることが目的ではありません。外した予測ほど記憶に残るので、直感で選んでください。
段数 × 1段の仕事、と数える
分割統治は3つの手順でできています。分ける、それぞれを解く、合わせる。小さくした問題もまた同じ手順で解くので、呼び出しは木の形に広がります。
この木を段ごとに横に切って見ると、計算量が読めます。
- 段数: 毎回半分にするなら、1 件になるまでの段数は log₂ n です。第11期の『半分にすると、なぜ20回で済むのか』で見た log がそのまま段数になります。
- 1段の仕事: その段にある部分問題すべての「合わせる」手間の合計です。
全体の仕事は、各段の仕事を上から下まで足したものです。マージソートでは、どの段を切っても合わせる対象は全部で n 件あります。並べ替える件数は分けても減らないからです。各段の仕事はおよそ n、段数が log₂ n なので、合計は n log₂ n 程度になります。
- ・合わせる仕事のある段は log2(8) = 3 段。各段 8 件分で、合計 3 × 8
- ・分ける数が2で、各段の仕事が変わらないから n log n になる
マージソートの比較回数を数える
マージソートの比較回数を Python で数えました(乱数で作った float の列、種は固定。Docker python:3.14-slim、Python 3.14.7 / aarch64 Linux、2026-10-07 取得)。
python 3.14.7 aarch64 Linuxmerge sort n=1000: comparisons=8714 n*log2(n)=9965.8 ratio=0.874 worst-case bound=8977merge sort n=10000: comparisons=120480 n*log2(n)=132877.1 ratio=0.907 worst-case bound=123617
| n | 比較回数 | n log₂ n | 比 |
|---|---|---|---|
| 1,000 | 8,714 | 9,965.8 | 0.87 |
| 10,000 | 120,480 | 132,877.1 | 0.91 |
n=1,000 では段数が 10(2^10 = 1,024)で、1段の比較は高々 1,000 回です。合計 10,000 回を超えないという見積もりの内側に、実測の 8,714 回が入っています。比較回数は機械の速さに依らない値なので、同じ種なら手元でも同じ数が出ます(macOS 26 / Python 3.14.6 でも 8,714 でした)。
「合わせる」手順そのもの、つまり2つの整列済みの列を1本にするマージが正しいことは、この期の初回で扱う不変式で言えます。ここでは正しさは任せて、回数だけを段ごとに数えています。
マージソートの比較回数が n log₂ n 程度に収まる理由として、最も適切なものはどれですか。
どの段が重いかで、答えは3通りに分かれる
マージソートは「各段の仕事が同じ」例でした。しかし、段を下りるごとに仕事が増えることも減ることもあります。その場合、全体を決めるのは一番重い端です。
| 段ごとの仕事 | 全体を支配するもの |
|---|---|
| 下るほど減る | 根(一番上の段)の仕事 |
| どの段も同じ | 段数 × 1段の仕事 |
| 下るほど増える | 葉の数 |
この3分岐を式で書いたものがマスター定理です。ここでは式は扱いません。無料で読める Jeff Erickson の講義ノート Algorithms の Appendix II "Solving Recurrences"(2026-10-07 取得)が、この直観を段ごとの和として説明しています。下るほど減る例としては乱択選択を挙げています。
This geometric series is dominated by its initial term n, so T(n) = Θ(n).
下るほど増える例が、次に見る Karatsuba の掛け算です。
This geometric series is dominated by its final term (3/2)^L n. Each leaf contributes 1 to this term; thus, the final term is equal to the number of leaves in the tree!
(PDF からテキストを抜き出したため、上付き文字は平文になっています。)
葉の数は「1段で何個に分かれるか」を段数の回数だけ掛けた数です。2つに分けるか3つに分けるかで、指数が変わります。
Karatsuba の掛け算 — 4回を3回にすると葉が減る
2桁どうしの 12 × 34 を、上の桁と下の桁に分けて考えます。素直にやると 1×3、1×4、2×3、2×4 の4回の掛け算が要ります。Karatsuba と Ofman の名で 1962 年に発表された方法は、これを3回にします。
- z2 = 1 × 3 = 3
- z0 = 2 × 4 = 8
- z1 = (1 + 2) × (3 + 4) − z2 − z0 = 21 − 3 − 8 = 10
- 答え = 3 × 100 + 10 × 10 + 8 = 408
1段で部分問題が3つになり、桁数が半分になります。2^k 桁なら k 段で1桁に届き、葉は 3^k 個です。1桁の掛け算の回数を数えました(環境は上と同じ)。
k digits school(4^k) karatsuba(3^k)1 2 4 (4) 3 (3) karatsuba_value_correct=True2 4 16 (16) 9 (9) karatsuba_value_correct=True3 8 64 (64) 27 (27) karatsuba_value_correct=True4 16 256 (256) 81 (81) karatsuba_value_correct=True5 32 1024 (1024) 243 (243) karatsuba_value_correct=True6 64 4096 (4096) 729 (729) karatsuba_value_correct=Truelog2(3) = 1.584962500721156
筆算は正確に 4^k 回、Karatsuba は正確に 3^k 回です。桁数を n = 2^k とすると、3^k は n の log₂3 乗、およそ n^1.585 です。64桁で 729 / 4,096 ≈ 0.178 倍でした。(x1 + x0 は1桁増えることがありますが、この勘定では半分の桁として数えています。積の値が x × y と一致することは確かめています。)
CPython の多倍長整数は、実際にこの方法へ切り替えます。Objects/longobject.c(3.14 ブランチ)より。
/* For int multiplication, use the O(N**2) school algorithm unless
* both operands contain more than KARATSUBA_CUTOFF digits (this
* being an internal Python int digit, in base BASE).
*/
#define KARATSUBA_CUTOFF 70
#define KARATSUBA_SQUARE_CUTOFF (2 * KARATSUBA_CUTOFF)
70 の単位は内部の digit(基数 BASE)であって、10進の桁ではありません。小さい数では筆算に落とします。k_mul の中にこうあります。
/* Use gradeschool math when either number is too small. */
i = a == b ? KARATSUBA_SQUARE_CUTOFF : KARATSUBA_CUTOFF;
if (asize <= i) {
a == b、つまり掛ける2つが同じもの(2乗)のときは、閾値が KARATSUBA_SQUARE_CUTOFF(KARATSUBA_CUTOFF の2倍)になります。
葉の数で勝っても、足し算や分割の手間は段ごとに乗ります。小さい問題では、その手間のほうが重いということです。
Karatsuba の工夫を使わず、半分の桁の掛け算を素直に4回するように分割したとします。1桁の掛け算の回数はどうなりますか。
マージソート(2つに分け、合わせる仕事が n)
どの段でも合わせる対象は合計 n 件。各段が同じ重さなので、段数 × n で n log₂ n。n=1,000 の比較回数は 8,714 回で、n log₂ n の 0.87 倍でした。
Karatsuba(3つに分け、桁は半分)
1段下りるごとに部分問題が3倍、大きさは半分。下の段ほど仕事が増え、葉の数 3^k が支配します。64桁で1桁の掛け算は 729 回、筆算は 4,096 回でした。
同じく半分ずつ分ける2つの手法で、なぜ片方は n log n、もう片方は n の 1.585 乗になるのでしょうか。
段数はどちらも同じです。1段下りたとき、部分問題の個数が何倍に、大きさが何分の1になるかを比べてください。
この章のまとめ
- 分割統治の計算量は、再帰木を段ごとに切り、各段の仕事を足して読む。 半分ずつなら段数は log₂ n。
- 各段が同じ重さなら 段数 × 1段の仕事。 マージソートは n=1,000 で 8,714 回、n log₂ n の 0.87 倍。
- 下の段ほど重いなら葉の数が支配する。 Karatsuba は部分問題を3つにして葉が 3^k、n^1.585 程度。4つのままなら n² に戻る。
- 根・各段・葉のどれが重いかの3分岐がマスター定理の直観。式は教科書で確かめる。
- CPython は KARATSUBA_CUTOFF 70(単位は内部 digit)を超えるまで筆算を使う。
- 既存クイズでは、「アルゴリズムとデータ構造」の algorithm-19・algorithm-6、「II(応用編)」の algorithm-2-10・algorithm-2-13 がこの章の結論の一行版です。
- CLRS(『アルゴリズムイントロダクション』)の目次や索引で divide-and-conquer(分割統治) を探すと、この回の内容に対応する章や節が見つかります。章の題と番号は版で変わるので、手元の目次で確かめてください。
自分の現場で確かめる
読んだだけでは身につきません。手元の環境で実際に見てみてください。
理解度チェック
読んだ直後は「分かった」と感じやすいものです。実際に解いて確かめてください。
CPython の Objects/longobject.c には KARATSUBA_CUTOFF 70 と定義されています。この 70 の単位はどれですか。
用語集(4語)
- 分割統治
- 問題を小さな同じ形の問題に分け、それぞれを解き、答えを合わせる手法。計算量は、分ける数・小さくなる割合・合わせる手間の3つで決まる。
- 再帰木
- 再帰の呼び出しを木として描いたもの。根が元の問題、各段がその深さの部分問題の集まり、葉がそれ以上分けない最小の問題。段ごとの仕事を足すと全体の仕事になる。
- 葉の数
- 再帰木の一番下にある部分問題の個数。1段で a 個に分かれ、段数が L なら a の L 乗。下の段ほど仕事が増える再帰では、これが全体を支配する。
- マスター定理
- 分割統治の再帰式を、根が支配・各段が同じ・葉が支配の3通りに分けて解く定理。教材では直観だけを扱い、正確な条件は教科書に送る。