この記事は、分割統治法で現れる再帰式をLaTeXで整理するためのメモです。主に置換法、再帰木法、マスター定理を扱います。
1. 置換法（Substitution Method）#
置換法では、まず解の上界または下界を予想し、数学的帰納法でその予想を証明します。再帰式に漸近記法をそのまま代入すると定数項を失うことがあるため、証明では適切な係数と余項を置くことが重要です。
例として、マージソート型の再帰式を考えます。
$$ T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n) $$解の形をT(n) = O(n log n)と予想し、より具体的にはT(n) ≤ c n log n - d nのような形を置きます。帰納法の仮定を代入すると、
となります。cを十分大きく選び、dや基底条件を調整すると、予想した上界を保てます。n=1やn=2などの基底条件も別に確認します。
Θ(1)を機械的に足し引きすると、定数項の情報が失われる場合があります。漸近記法は便利ですが、帰納法の不等式を厳密に保つための定数を別に置いてください。2. 再帰木法（Recursion-Tree Method）#
再帰木法では、再帰式を木として展開し、各レベルのコストを合計します。一般形
$$ T(n)=aT(n/b)+f(n) $$では、レベルjの部分問題数はa^j、各部分問題のサイズはn/b^jです。深さはおおよそlog_b nになります。
各レベルの合計コストを比較し、根から葉までの和を求めます。各レベルのコストが同じなら深さの分だけ増え、根に近いレベルが支配的なら根のコストに近い計算量になります。
3. マスター定理（Master Theorem）#
再帰式
$$ T(n)=aT(n/b)+f(n) $$について、a ≥ 1、b > 1とします。比較対象は
です。これは再帰木の各レベルに現れる部分問題の総数とサイズから得られる境界の関数です。
Case 1：f(n)が小さい#
あるε > 0について、
なら、
$$ T(n)=\Theta\left(n^{\log_b a}\right) $$です。
Case 2：同じ程度#
あるk ≥ 0について、
なら、
$$ T(n)=\Theta\left(n^{\log_b a}\log^{k+1}n\right) $$です。
Case 3：f(n)が大きい#
あるε > 0について、
かつ正則性条件
$$ af(n/b) \leq cf(n), \qquad c<1 $$が十分大きなnで成立するなら、
です。
4. マスター定理の展開#
再帰木を展開すると、非再帰部分の合計は概念的に次のようになります。
$$ \sum_{j=0}^{\lfloor\log_b n\rfloor} a^j f\left(\frac{n}{b^j}\right) $$さらに葉のコストとしてΘ(n^{log_b a})が加わります。どの項が支配的かを調べることで、Case 1からCase 3の結果が得られます。
5. LaTeXで式を書く例#
\begin{align}
T(n) &= 2T\left(\frac{n}{2}\right) + \Theta(n) \\
&= \Theta(n\log n)
\end{align}場合分けは次のように書けます。
\begin{cases}
\Theta(1), & 0 \le n < 1, \\
aT(n/b)+f(n), & n \ge 1.
\end{cases}まとめ#
- 置換法は、予想した計算量を帰納法で証明する。
- 再帰木法は、各レベルのコストを可視化して合計する。
- マスター定理は、
f(n)とn^{log_b a}を比較して再帰式を分類する。 - 厳密な証明では、漸近記法で隠れる定数項と基底条件を忘れない。