分割統治再帰のための高度なマスター定理

分割統治は、問題を同様のタイプの複数のサブ問題に再帰的に分解することに基づいたアルゴリズムであり、これらのサブ問題は簡単に解決できます。

例

分割統治手法をより深く理解するために例を挙げてみましょう -

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

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

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

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

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

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

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

このような場合、時間計算量を求めるためのマスター定理は効率的ではないため、再帰的再帰のための高度なマスター定理が設計されました。これは、-

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

の形式の再帰問題を処理するように設計されています。 n は問題の規模です。

a = 再帰内の部分問題の数、a > 0

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

このタイプの問題を解決するには、次の解決策を使用します:

• If a > b_k, then T(n) = ∅ ( nlogba)
• If a = b_k, then
  • If p > -1, then T(n) = ∅(nlogba log^{p 1}n )
  • p = -1 の場合、T(n) = ∅(nlog_ba loglogn)
  • p ba)
• If a k, then
  • if p > = 0 , then T(n) = ∅(n_klog_pn)
  • p

高レベルのマスター アルゴリズムを使用して、いくつかのアルゴリズムの複雑さを計算します。 -

二分探索 - t(n) = θ ( logn)

マージソート − T(n) = θ(nlogn)

以上が分割統治再帰のための高度なマスター定理の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。