マスター定理（アルゴリズムの分析）

アルゴリズムの解析において、分割統治法の再帰に対するマスター定理は、分割統治法アルゴリズムの解析で発生する多くの再帰関係の漸近解析を提供します。このアプローチは、 1980年にジョン・ベントレー、ドロテア・ブロスタイン（旧姓ハーケン）、ジェームズ・B・サックスによって初めて発表され、そのような再帰を解く「統一的な方法」として説明されました。^{[1] 「マスター定理」という名前は、}コーメン、レイザーソン、リベスト、スタインによる広く使用されているアルゴリズムの教科書「アルゴリズム入門」によって普及しました。

この定理ではすべての再帰関係を解けるわけではありません。この定理の一般化には、Akra-Bazzi法が含まれます。

次のような 再帰アルゴリズムを使用して解決できる問題を考えてみましょう。

手順p(サイズnの入力x ):
     n < 定数kの場合: 再帰なしでxを直接
    
        解きます。xのサブ問題を
        作成します。それぞれのサイズはn / bです。各サブ問題に対して
        手順p を再帰的に呼び出します。
        サブ問題の結果を組み合わせる

上記のアルゴリズムは、問題を再帰的にいくつかのサブ問題に分割します。各サブ問題のサイズはn / bです。その解ツリーには各再帰呼び出しのノードがあり、そのノードの子はその呼び出しから行われた他の呼び出しです。ツリーのリーフは再帰の基本ケース、つまり再帰しないサブ問題 (サイズがk未満) です。上記の例では、リーフ以外の各ノードに子ノードがあります。各ノードは、再帰呼び出しのインスタンスに渡され、 によって与えられるサブ問題のサイズnに対応する量の作業を行います。アルゴリズム全体で行われる作業の総量は、ツリー内のすべてのノードによって実行される作業の合計です。 ${\displaystyle f(n)}$

上に示したpのようなアルゴリズムの実行時間は、通常 と表記されるサイズnの入力に対して、再帰関係によって表現できる。${\displaystyle T(n)}$

${\displaystyle T(n)=a\;T\left({\frac {n}{b}}\right)+f(n),}$

ここで、上記の手順でサブ問題を作成し、その結果を組み合わせるのにかかる時間です。この式は、連続的にそれ自体に代入して展開することで、行われた作業の総量を表す式を得ることができます。^[2]マスター定理により、この形式の多くの再帰関係を、再帰関係の展開を行わずに Θ 表記に直接変換できます。${\displaystyle f(n)}$

マスター定理は、入力を同じサイズのより小さなサブ問題に分割し、サブ問題を再帰的に解決し、サブ問題のソリューションを組み合わせて元の問題のソリューションを提供する分割統治アルゴリズムからの再帰に対して、常に漸近的に厳しい境界をもたらします。このようなアルゴリズムの時間は、再帰の最上位レベルで実行される作業 (問題をサブ問題に分割し、サブ問題のソリューションを組み合わせる) と、アルゴリズムの再帰呼び出しにかかる時間を加算することで表すことができます。 がサイズ の入力に対するアルゴリズムの合計時間を表し、 が再帰の最上位レベルでかかる時間を表す場合、時間は次の形式を取る再帰関係で表すことができます。 ${\displaystyle T(n)}$${\displaystyle n}$${\displaystyle f(n)}$

${\displaystyle T(n)=a\;T\!\left({\frac {n}{b}}\right)+f(n)}$

ここで、は入力問題のサイズ、は再帰内のサブ問題の数、 は各再帰呼び出し ( )でサブ問題のサイズが縮小される係数です。 重要なのは、とは に依存してはならないということです。 以下の定理では、再帰の基本ケースとして、がある境界 より小さい場合、再帰呼び出しにつながる最小の入力サイズ になること も想定しています。${\displaystyle n}$${\displaystyle a}$${\displaystyle b}$${\displaystyle b>1}$${\displaystyle a}$${\displaystyle b}$${\displaystyle n}$${\displaystyle T(n)=\Theta (1)}$${\displaystyle n}$${\displaystyle \kappa >0}$

この形式の再発は、問題を分割/再結合する作業が臨界指数とどのように関係しているかに基づいて、次の 3 つの領域のいずれかを満たすことがよくあります。(以下の表では、標準的なビッグ O 表記法を使用しています)。 ${\displaystyle f(n)}$ ${\displaystyle c_{\operatorname {crit} }=\log _{b}a}$

${\displaystyle c_{\operatorname {crit} }=\log _{b}a=\log(\#{\text{サブ問題}})/\log({\text{相対的なサブ問題のサイズ}})}$

ケース2の便利な拡張は、のすべての値を処理します。^[3]${\displaystyle k}$

${\displaystyle T(n)=8T\left({\frac {n}{2}}\right)+1000n^{2}}$

上記の式からわかるように、

${\displaystyle a=8,\,b=2,\,f(n)=1000n^{2}}$、 それで

${\displaystyle f(n)=O\left(n^{c}\right)}$、 どこ${\displaystyle c=2}$

次に、ケース 1 の条件を満たしているかどうかを確認します。

${\displaystyle \log _{b}a=\log _{2}8=3>c}$。

マスター定理の最初のケースから、

${\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\right)=\Theta \left(n^{3}\right)}$

(この結果は、 と仮定して、となる再帰関係の正確な解によって確認されます)。 ${\displaystyle T(n)=1001n^{3}-1000n^{2}}$${\displaystyle T(1)=1}$

${\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+10n}$

上記の式からわかるように、変数は次の値を取得します。

${\displaystyle a=2,\,b=2,\,c=1,\,f(n)=10n}$

${\displaystyle f(n)=\Theta \left(n^{c}\log ^{k}n\right)}$どこ${\displaystyle c=1,k=0}$

次に、ケース 2 の条件を満たしているかどうかを確認します。

${\displaystyle \log _{b}a=\log _{2}2=1}$であり、したがってcとcは等しい。${\displaystyle \log _{b}a}$

したがって、マスター定理の 2 番目のケースから次のようになります。

${\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\log ^{k+1}n\right)=\Theta \left(n^{1}\log ^{1}n\right)=\Theta \left(n\log n\right)}$

したがって、与えられた再帰関係は でした。 ${\displaystyle T(n)}$${\displaystyle \Theta (n\log n)}$

(この結果は、 と仮定して、となる再帰関係の正確な解によって確認されます)。 ${\displaystyle T(n)=n+10n\log _{2}n}$${\displaystyle T(1)=1}$

${\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+n^{2}}$

上記の式からわかるように、変数は次の値を取得します。

${\displaystyle a=2,\,b=2,\,f(n)=n^{2}}$

${\displaystyle f(n)=\Omega \left(n^{c}\right)}$、 どこ${\displaystyle c=2}$

次に、ケース 3 の条件を満たしているかどうかを確認します。

${\displaystyle \log _{b}a=\log _{2}2=1}$したがって、はい、${\displaystyle c>\log _{b}a}$

正則性条件は次の通りです:

${\displaystyle 2\left({\frac {n^{2}}{4}}\right)\leq kn^{2}}$、選択${\displaystyle k=1/2}$

したがって、マスター定理の 3 番目のケースから次のようになります。

${\displaystyle T\left(n\right)=\Theta \left(f(n)\right)=\Theta \left(n^{2}\right).}$

したがって、与えられた再帰関係は であり、これは元の式の に準拠しています。 ${\displaystyle T(n)}$${\displaystyle \Theta (n^{2})}$${\displaystyle f(n)}$

(この結果は、 と仮定して、となる再帰関係の正確な解によって確認されます。) ${\displaystyle T(n)=2n^{2}-n}$${\displaystyle T(1)=1}$

次の方程式はマスター定理では解けない: ^[4]

• ${\displaystyle T(n)=2^{n}T\left({\frac {n}{2}}\right)+n^{n}}$

  aは定数ではない。部分問題の数は固定されている必要がある。

• ${\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+{\frac {n}{\log n}}}$

  との非多項式差（下記参照；拡張版が適用）${\displaystyle f(n)}$${\displaystyle n^{\log _{b}a}}$

• ${\displaystyle T(n)=64T\left({\frac {n}{8}}\right)-n^{2}\log n}$

  ${\displaystyle f(n)}$結合時間であるが正ではない

• ${\displaystyle T(n)=T\left({\frac {n}{2}}\right)+n(2-\cos n)}$

  ケース3ですが規則性違反です。

上記の 2 番目の不適切な例では、との差は比 で表すことができます。任意の定数 に対して であることは明らかです。したがって、差は多項式ではなく、マスター定理の基本形式は適用されません。拡張形式 (ケース 2b) は適用され、解 が得られます。 ${\displaystyle f(n)}$${\displaystyle n^{\log _{b}a}}$${\displaystyle {\frac {f(n)}{n^{\log _{b}a}}}={\frac {n/\log n}{n^{\log _{2}2}}}={\frac {n}{n\log n}}={\frac {1}{\log n}}}$${\displaystyle {\frac {1}{\log n}}<n^{\epsilon }}$${\displaystyle \epsilon >0}$${\displaystyle T(n)=\Theta (n\log \log n)}$

• アクラ・バッツィ法
• 漸近的複雑性

• Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein。アルゴリズム入門、第 2 版。MIT Press および McGraw–Hill、2001 年。ISBN 0-262-03293-7 。セクション 4.3 (マスター メソッド) と 4.4 (マスター定理の証明)、pp. 73–90。 
• Michael T. GoodrichおよびRoberto Tamassia著「アルゴリズム設計: 基礎、分析、およびインターネットの例」Wiley、2002 年、ISBN 0-471-38365-1。マスター定理 (CLRS のものよりも強力な、ここに含まれるケース 2 のバージョンを含む) は、268 ～ 270 ページにあります。