マスター定理は、分割統治アルゴリズムの分析で生じる漸化式を解くために使用されるツールです。マスター定理は、次の形式の漸化関係を解く体系的な方法を提供します。

T(n) = aT(n/b) + f(n)

1. ここで、a、b、f(n) は正の関数で、n は問題のサイズです。マスター定理は、ある定数 k に対して漸化式の解が O(n^k) の形になる条件を提供し、k の値を決定する式を与えます。
2. マスター定理の上級バージョンは、基本形式よりも複雑な漸化式を処理できる、より一般的な形式の定理を提供します。マスター定理の高度なバージョンでは、複数の項とより複雑な関数を含む漸化式を処理できます。
3. マスター定理はすべての漸化式に適用できるわけではなく、特定の漸化式に対して常に正確な解が提供されるわけではないことに注意することが重要です。ただし、これは分割統治アルゴリズムの時間計算量を分析するのに便利なツールであり、より複雑な反復を解決するための良い出発点となります。

マスター定理は、漸近表記の観点からアルゴリズム (分割統治アルゴリズム) の実行時間を決定するために使用されます。
再帰を使用して解決される問題を考えてみましょう。

 function f (input x size n) if (n else divide x into a subproblems of size n/b call f recursively to solve each subproblem Combine the results of all sub-problems>

上記のアルゴリズムは問題を次のように分割します。 ある それぞれのサイズが n/b の部分問題を作成し、それらを再帰的に解決して問題を計算します。問題に対して実行される追加の作業は f(n) によって与えられます。つまり、部分問題を作成し、上記の手順でその結果を結合する時間です。

したがって、マスター定理によれば、上記のアルゴリズムの実行時間は次のように表すことができます。

 T(n) = aT(n/b) + f(n)>

ここで、n = 問題のサイズ
a = 再帰内の部分問題の数、および a>= 1
n/b = 各部分問題のサイズ
f(n) = 部分問題への分割など、再帰呼び出し以外で行われる作業のコストと、解を得るためにそれらを結合するコスト。

すべての漸化式がマスター定理を使用して解決できるわけではありません。

• T(n) は単調ではありません。例: T(n) = sin n
• f(n) は多項式ではありません。例: T(n) = 2T(n/2) + 2ⁿ

この定理はマスター定理の発展版であり、回帰が次の形式である場合に分割統治アルゴリズムの実行時間を決定するために使用できます。

ここで、n = 問題のサイズ
a = 再帰内の部分問題の数、および a>= 1
n/b = 各部分問題のサイズ
b> 1、k>= 0、p は実数です。

それから、

1. a> b の場合^k、T(n) = θ(n^{ログ_bある}）
2. a = b の場合^k、 それから
   (a) p> -1 の場合、T(n) = θ(n^{ログ_bある}ログ^p+1n)
   (b) p = -1 の場合、T(n) = θ(n^{ログ_bある}ログログン）
   (c) p <-1 の場合、T(n) = θ(n^{ログ_bある})
   
3. もし ｋ、それでは
   (a) p>= 0 の場合、T(n) = θ(n^kログ^pn)
   (b) p <0 の場合、T(n) = θ(n^k)
   

時間計算量の分析 –

例-1: 二分探索 – T(n) = T(n/2) + O(1)
a = 1、b = 2、k = 0、p = 0
b^k= 1. したがって、a = b^kおよび p> -1 [ケース 2.(a)]
T(n) = θ(n^{ログ_bある}ログ^p+1n)
T(n) = θ(logn) 例-2: マージソート – T(n) = 2T(n/2) + O(n)
a = 2、b = 2、k = 1、p = 0
b^k= 2. したがって、a = b^kおよび p> -1 [ケース 2.(a)]
T(n) = θ(n^{ログ_bある}ログ^p+1n)
T(n) = θ(nlogn) 例-3: T(n) = 3T(n/2) + n²
a = 3、b = 2、k = 2、p = 0
b^k= 4. したがって、 k および p = 0 [ケース 3.(a)]
T(n) = θ(n^kログ^pn)
T(n) = θ(n²）

例-4: T(n) = 3T(n/2) + log²n
a = 3、b = 2、k = 0、p = 2
b^k= 1. したがって、a> b^k【事例1】
T(n) = θ(n^{ログ_bある})
T(n) = θ(n^ログ₂3)

例-5: T(n) = 2T(n/2) + nlog²n
a = 2、b = 2、k = 1、p = 2
b^k= 2. したがって、a = b^k【事例2.(a)】
T(n) = θ(n^{ログ_bある}ログ^p+1n)
T(n) = θ(n^ログ₂2ログ³n)
T(n) = θ(nlog³n)

例-6: T(n) = 2ⁿT(n/2) + nⁿ
関数の形式が T(n) = aT(n/b) + θ(n^kログ^pn)

GATE 練習問題 –

• GATE-CS-2017 (セット 2) |質問56
• ゲートイット2008 |質問42
• ゲートCS2009 |質問35

マスター定理に関して留意すべき重要な点がいくつかあります。

1. 分割統治の漸化式: マスター定理は、分割統治アルゴリズムの分析で生じる漸化式を解決するために特別に設計されています。
2. 漸化式の形式: マスター定理は、T(n) = aT(n/b) + f(n) の形式の漸化式に適用されます。ここで、a、b、f(n) は正の関数で、n はサイズです。問題の。
3. 時間計算量: マスター定理は、ある定数 k に対して漸化式の解が O(n^k) の形式になる条件を提供し、k の値を決定する式を与えます。
4. 上級バージョン: マスター定理の上級バージョンでは、基本形式よりも複雑な漸化式を処理できる、より一般的な形式の定理が提供されます。
5. 制限事項: マスター定理はすべての漸化式に適用できるわけではなく、特定の漸化式に対して常に正確な解が提供されるとは限りません。
6. 便利なツール: マスター定理は、制限はありますが、分割統治アルゴリズムの時間計算量を分析するための便利なツールであり、より複雑な漸化式を解くための良い出発点となります。
7. 他の手法による補足: 場合によっては、特定の漸化式を完全に解くために、置換法や反復法などの他の手法でマスター定理を補足する必要がある場合があります。