データ構造における置換法：漸化式の解き方を二分探索・マージソートで解説

置換法（代入法）による漸化式の解き方

アルゴリズムの計算量を評価する際、再帰的な処理の実行時間は「漸化式」として表されることがあります。本記事では、置換法（代入法）を用いて漸化式を解き、計算量を導出する手順を解説します。理解を深めるために、二分探索とマージソートという2つの代表的なアルゴリズムを例に取り上げます。

例1：二分探索の計算量

まずは二分探索（バイナリサーチ）から見ていきましょう。二分探索では、配列の中央に目的の要素が存在するかどうかを確認します。中央に存在すればアルゴリズムは終了し、存在しない場合は、元の配列の左半分または右半分の部分配列に対して同じ操作を繰り返します。そのため、各ステップで配列のサイズは n/2 ずつ減少していきます。

二分探索アルゴリズムの実行時間を T(n)、ベースケース（基本条件）の処理時間を O(1) とすると、漸化式は次のように表せます。

$$T(n)=\begin{cases}T(1) & for\:n \leq 1\\T(\frac{n}{2})+c & for\:n > 1\end{cases}$$

解法：式を1ステップずつ繰り返し代入して結果を求めます。

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

T(n/2) を代入すると、

$$T(n)=(T(\frac{n}{4})+c)+c$$

$$T(n)=T(\frac{n}{4})+2c$$

$$T(n)=T(\frac{n}{8})+3c$$

$$T(n)=T(\frac{n}{2^{k}})+kc$$

n / 2^k が 1 に到達した時点で、2^k = n が成り立っていることを意味します。したがって、k = log₂n となります。

よって、T(n) の計算量は ϴ(log n) です。

例2：マージソートの計算量

次に、マージソートの例を見ていきます。マージソートでは、リストを2つの部分に分割し、サイズが1になるまで分割を繰り返します。その後、それらをソート済みの順序でマージ（併合）していきます。このマージ処理には O(n) の時間がかかります。

マージソート全体の実行時間を T(n) とすると、リストを2つの半分に分割してそれぞれに同じ処理を行うため、各部分の処理時間は T(n/2) となります。したがって、漸化式は次のようになります。

$$T(n)=\begin{cases}T(1) & for\:n = 1\\2T(\frac{n}{2})+cn & for\:n > 1\end{cases}$$

解法：同様に、式を1ステップずつ代入していきます。

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

T(n/2) を代入すると、

$$T(n)=2(2T(\frac{n}{4})+\frac{cn}{2})+cn$$

$$T(n)=4T(\frac{n}{4})+2cn$$

$$T(n)=8T(\frac{n}{8})+3cn$$

$$T(n)=2^{k}T(\frac{n}{2^{k}})+kcn$$

ここでも n / 2^k が 1 になると、2^k = n、すなわち k = log₂n が得られます。これを代入すると、T(n) は次のようになります。

T(n) = nT(1) + cn log₂n

よって、計算量は θ(n log n) となります。

まとめ

置換法では、漸化式を繰り返し代入してパターンを見つけ、一般形を求めたうえで、n / 2^k = 1 となる条件から k の値を確定させることで計算量を導出します。「半分だけを1回調べる」二分探索は対数時間 ϴ(log n)、「半分を2つに分けて両方を処理する」マージソートは θ(n log n) という結果になり、この対比を押さえておくことが重要です。