分割統治法の高度なマスター定理とは？再帰アルゴリズムの計算量解析を徹底解説

分割統治法（Divide and Conquer）とは

分割統治法とは、元の問題を同種のより小さな部分問題へ再帰的に分割し、それぞれを個別に解決することで全体の解を導くアルゴリズムのパラダイムです。

具体例

分割統治法の仕組みを理解するために、以下の疑似コードを見てみましょう。

function recursive(input x size n)
    if(n < k)
        入力をサイズ n/p の m 個の部分問題に分割し、
        各部分問題に対して f を再帰的に呼び出す
    else
        x を解いて返す

すべての部分問題の結果を統合し、元の問題の解として返します。

解説： 上記の処理では、問題全体をより簡単に解ける小さな部分問題へ分割し、それぞれを再帰的に解いていく流れになっています。

マスター定理とは

分割統治法におけるマスター定理は、再帰関係を持つアルゴリズムの計算量（ビッグオー記法）を求めるための解析定理です。アルゴリズムの実行時間を漸近記法の形で表す際に使用されます。

先ほどの例における実行時間の漸化式は次のようになります。

T(n) = f(n) + m・T(n/p)

マスター定理が適用できないケース

多くの再帰アルゴリズムではマスター定理を用いて時間計算量を求められますが、適用できないケースも存在します。代表的な例は以下のとおりです。

• 問題 T(n) が単調でない場合（例：T(n) = sin n）
• 問題の関数 f(n) が多項式で表せない場合

これらのケースでは通常のマスター定理がうまく機能しないため、より広範な再帰漸化式に対応した高度なマスター定理が考案されました。

高度なマスター定理の定義

高度なマスター定理は、次の形式の漸化式を扱うために設計されています。

T(n) = aT(n/b) + Θ((n^k)・log^p n)

各パラメータの意味は以下のとおりです。

• n：問題のサイズ
• a：再帰における部分問題の数（a > 0）
• n/b：各部分問題のサイズ（b > 1）
• k：0 以上の整数（k ≥ 0）
• p：実数

計算量を求めるための条件分岐

この形式の漸化式を解くには、パラメータの関係に応じて以下のケースを使い分けます。

• a > b^k の場合： T(n) = Θ(n^log_ba)
• a = b^k の場合：
  • p > -1 のとき：T(n) = Θ(n^log_ba・log^p+1n)
  • p = -1 のとき：T(n) = Θ(n^log_ba・log log n)
  • p < -1 のとき：T(n) = Θ(n^log_ba)
• a < b^k の場合：
  • p ≥ 0 のとき：T(n) = Θ(n^k・log^pn)
  • p < 0 のとき：T(n) = Θ(n^k)

具体例による計算量の算出

高度なマスター定理を用いて、代表的なアルゴリズムの計算量を求めてみましょう。

• 二分探索（バイナリサーチ）： T(n) = Θ(log n)
• マージソート： T(n) = Θ(n log n)

このように、高度なマスター定理を活用すれば、通常のマスター定理では扱えない漸化式に対しても、体系的に時間計算量を導出できます。