漸化式

漸化式は、再帰的アルゴリズムの実行時間を、より小さな入力に対する実行時間で表現するものです。これを解くことで、分割統治法やその他の再帰的アルゴリズムの解析に用いられる閉形式の漸近的上限が得られます。

Definition

漸化式とは、関数の値を、より小さな入力におけるその値によって定義する方程式です。アルゴリズム解析においては、サイズnの入力に対するアルゴリズムのコストを、より小さな部分問題に対するコストで表現します。

Scope

このトピックでは、アルゴリズム解析で生じる漸化式の定式化と解法について扱います。具体的には、代入法、再帰木法、およびT(n) = aT(n/b) + f(n)の形式の分割統治漸化式に対するマスター定理について説明します。各再帰的アルゴリズムがどのように漸化式を導き出すか、そしてその漸化式をどのようにビッグシータ記法に変換するかを解説します。漸近記法自体は別途扱われるため、このトピックには含まれません。また、離散数学における組み合わせ的母関数法も除外します。

Core questions

• 再帰的アルゴリズムは、その実行時間に対する漸化式をどのように生み出すのでしょうか？
• 代入法は、推測された解を証明し検証するためにどのように使用されるのでしょうか？
• 再帰木法は、再帰レベル全体での総作業量をどのように明らかにするのでしょうか？
• マスター定理はいつ適用され、その3つのケースは何を意味するのでしょうか？
• マスター定理の形式に当てはまらない漸化式はどのように扱われるのでしょうか？

Key concepts

• 漸化式
• 代入法
• 再帰木法
• マスター定理
• 分割統治漸化式
• 基本ケースと再帰ケース
• 閉形式解
• Akra-Bazzi法

Key theories

マスター定理

分割統治漸化式 T(n) = aT(n/b) + f(n) に対して、マスター定理は f(n) を n の log b 底 a 乗と比較することで漸近解を与えます。これは、葉、根、またはバランスの取れたレベルが支配的である3つのケースをカバーします。

再帰木法と代入法

再帰木法は、再帰の各レベルで行われる作業を合計して上限を示唆し、代入法はそれを帰納法によって厳密に証明します。これらを組み合わせることで、マスター定理の範囲を超える漸化式も扱うことができます。

Clinical relevance

漸化式の解法は、マージソートやクイックソートから高速乗算、そして多くの動的計画法に至るまで、再帰的アルゴリズムの実行時間を導き出す標準的な方法です。エンジニアや研究者は、マスター定理を日常的に使用して、これらのアルゴリズムに付随する漸近的複雑性の主張を導き出し、正当化しています。

History

アルゴリズムの漸化式解析は、クヌースの『The Art of Computer Programming』で体系化されました。マスター定理はCLRSを通じて教科書の定番となり、Akra-Bazzi法（1998年）は、不均一な分割を持つより広範な分割統治漸化式に一般化されました。

Key figures

• Donald Knuth
• Mohamad Akra
• Louay Bazzi

Seminal works

• cormen2009
• knuth1997vol1

Frequently asked questions

マスター定理はいつ使用できますか？

マスター定理は、T(n) = aT(n/b) + f(n) の形式の漸化式に適用されます。ここで a >= 1 および b > 1 であり、各レベルで問題をサイズ n/b の a 個の部分問題に分割します。不均一な分割、変動する部分問題サイズ、または非多項式的な結合コストを持つ漸化式には、代わりに再帰木法、代入法、またはAkra-Bazzi法が必要となる場合があります。

マージソートの漸化式がO(n log n)になるのはなぜですか？

マージソートは T(n) = 2T(n/2) + O(n) を導きます。これは、2つの半分のサイズの部分問題と線形のマージコストを意味します。この場合、再帰木のすべての log n レベルでレベルごとの作業量が同じであるため、合計は n に log n を掛けたものとなり、マスター定理によって Theta(n log n) であることが確認されます。