データ構造とアルゴリズム解析における漸化式の基礎

アルゴリズム解析と漸化式の関係

アルゴリズムの計算量を解析する際、漸化式(再帰関係式)が現れることがよくあります。漸化式とは、式の中に同じ関数自身が含まれる関係式のことです。特に、再帰的なアルゴリズムや分割統治法(divide and conquer)を用いるアルゴリズムの解析では、ほぼ必ずと言っていいほど漸化式が登場します。

ここでは、具体的な例を通じて、漸化式がどのように導かれるのかを見ていきましょう。

例1:二分探索の漸化式

まずは二分探索(binary search)を例に挙げます。二分探索では、まず配列の中央に目的の要素が存在するかどうかを確認します。中央に要素が見つかれば探索は終了し、見つからなければ左半分または右半分の部分配列に対して同じ操作を繰り返します。つまり、各ステップごとに配列のサイズは n/2 に減少していきます。

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

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

例2:マージソートの漸化式

次に、マージソート(merge sort)の例を見てみましょう。マージソートでは、リストを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}$$

漸化式の主な解法

これらの漸化式は、さまざまな手法を用いて解くことができます。代表的な解法は以下の通りです。

• 代入法(substitution method):解の形を推測し、数学的帰納法を用いてその正しさを証明する方法
• 再帰木法(recursion tree method):再帰呼び出しを木構造として可視化し、各レベルのコストを合計して計算量を求める方法
• マスター定理(Master theorem):特定の形式を持つ漸化式をテンプレート的に解くことができる特殊な定理

これらの解法を使いこなせるようになると、再帰アルゴリズムや分割統治法の計算量を効率的に評価できるようになり、より良いアルゴリズム設計につながります。