分割統治法の高度なマスター定理

分割統治法 は、問題を簡単に解決できる同様のタイプの複数のサブ問題に再帰的に分岐することに基づくパラダイムで機能するアルゴリズムです。

例

分割統治法の詳細を学ぶために例を見てみましょう-

function recursive(input x size n)
   if(n < k)
      Divide the input into m subproblems of size n/p.
      and call f recursively of each sub problem
   else
      Solve x and return

すべてのサブ問題の結果を組み合わせて、解決策を元の問題に戻します。

説明 −上記の問題では、問題セットは、簡単に解決できる小さなサブ問題に細分されます。

分割統治法のマスター定理 は、漸化式アルゴリズムのbig-0値を決定するために使用できる分析定理です。これは、アルゴリズムに必要な時間を見つけて、それを漸近表記形式で表すために使用されます。

上記の例の問題の実行時値の例-

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

ほとんどの再帰的アルゴリズムでは、マスターの定理を使用したアルゴリズムの時間計算量を見つけることができますが、マスターの定理が適用できない場合があります。これらは、マスターの定理が適用できない場合です。問題T（n）が単調でない場合、たとえば、T（n）=sinnです。問題関数f（n）は多項式ではありません。

これらの場合、時間計算量を見つけるためのマスター定理はホット効率的ではないため、再帰的再帰のための高度なマスター定理が設計されました。 -

T(n) = aT(n/b) + ø((n^k)logpn)

ここで、nは問題のサイズです。

a =再帰のサブ問題の数、a> 0

n / b=各サブ問題のサイズb>1、k> =0、pは実数です。

この種の問題を解決するために、次の解決策を使用します。

• a> b _kの場合 、次にT（n）=∅（nlogba）
• a =b _kの場合 、次に
  • p> -1の場合、T（n）=∅（nlogbalog ^{p + 1} n）
  • p =-1の場合、T（n）=∅（nlog _ba loglogn）
  • p <-1の場合、T（n）=∅（nlog _ba ）
• a kの場合 、次に
  • p> =0の場合、T（n）=∅（n _k log _p n）
  • p <0の場合、T（n）=∅（nk）