1. 序章

多くのアルゴリズムは、サイズの問題をより小さなサイズのサブ問題に分解することによって機能します。 二分探索マージソートなどのほとんどの分割統治アルゴリズムは、この性質のものです。 このようなアルゴリズムの実行時間は、自然に再帰シーケンスとしてモデル化されます。 このチュートリアルでは、特定の漸化式を解くためのクックブックメソッドであるマスター定理について説明します。

2. マスター定理のステートメント

サイズの大きな問題を次のように解決するアルゴリズムを考えてみましょう。

  1. 問題を小さなチャンクに分割し、それぞれのサイズ
  2. 小さなサブ問題を再帰的に解決します
  3. サブ問題の再結合

サイズの問題を解決するために行われた総作業とします。 問題をサブ問題に分割してから、サブ問題を再結合するコストを考えてみましょう–ステップ1と3。  コストはサイズに対応するため、はサイズのサブ問題に対応するコストです。 ステップ2では、このようなサブ問題を解決するため、ステップ2で実行される作業はに等しくなります。 すべてをまとめると、総作業量は次のように表すことができます。

   

2.1. 再発のあるアルゴリズムのランタイム

簡単にするために、最初に、次の形式を繰り返すアルゴリズムを考えます。

   

このアルゴリズムによって実行された作業の合計量の再帰ツリーは、次のようにグラフィカルに描画できます。

各初期ノードの実行時間はです。 このツリーは、底に達するまで、つまり、各小さなサブ問題がサイズの基本的な問題に縮小されるまで、さらに描画できます。

深さでは、各サブ問題はサイズを持ち、深さでは、各サブ問題はサイズを持ち、深さでは、各サブ問題はサイズを持ちます。 木の高さは、次の式で与えられます

   

したがって、ツリーには高さがあり、深さでは、ツリーにはノードがあります。 したがって、リーフノードがあります。 各リーフノードは、実行時間が一定または一定であるサイズ1の問題を表します。 したがって、合計実行時間はです。

2.2. マスター定理

直感的に言えば、漸近的に正の関数が漸化式に追加されると、次のようになります。

   

マスター定理は、との間の相対的な比較に基づいて、アルゴリズムの実行時間を推定することが可能であると主張しています。

マスター定理は次のように定義されます。フォームの繰り返しを考えると：

   

定数および漸近的に正の場合、次のステートメントが当てはまります。

  • ケース1。 の場合、いくつかの場合、。
  • ケース2。 の場合、。
  • ケース3。 ある場合とある定数の場合、

簡単に言えば、が多項式よりも小さい場合は、が支配的であり、アルゴリズムの実行時間はです。 が多項式よりも大きい場合は、が優勢であり、アルゴリズムの実行時間はです。 最後に、最終的にがと同じくらい速く成長する場合、アルゴリズムの実行時間はです。

2.3. 多項式的に大きいvs。 漸近的に大きい

マスター定理は、すべてのに対する解決策を提供するわけではありません。 特に、多項式の因数分解よりも小さいか大きい場合、3つのケースのいずれも満たされません。

多項式が大きいということは、関数の比率が2つの多項式の間に漸近的に収まるということです。 具体的には、次のような一般化された多項式（分数の指数が許可されます）が存在する場合に限り、は多項式よりも大きくなります。

   

たとえば、次の理由により、は漸近的に大きくなります。

   

.

ただし、多項式の因数より大きくはありません。 次のような多項式はありません。

   

この別の例は、です。これは、多項式よりも大きくはありません。 関数の成長が速すぎます。 。よりも指数関数的に大きくなります。 したがって、は漸近的により大きいが、次のような多項式はありません。

   

3. 例

最初の例として、再発について考えてみましょう。

   

この再発については、、、があります。 である量は、多項式よりも大きいので、マスター定理のケース1は、解がであるということを意味します。

次に、次のことを検討できます。

   

この再発については、、、があります。 量はと同じくらい速く増加するので、マスター定理のケース2は、解がであるということを意味します。

私達はまた見ることができます：

   

この再発については、、、があります。 に対する量の比率を見てみましょう。 比率の適切な多項式境界を見つけることができます。

   

したがって、は多項式よりも大きくなります。 マスター定理のケース3は、漸化式の解がであるということを意味します。

最後に、再発について考えてみましょう。

   

この再発に対して、、、およびがあります。 前に見たように、は漸近的に。よりも大きくなります。 ただし、多項式より大きくはありません。

4. マスター定理の証明

再発を分析しましょう：

   

ツリーのルートにはアドオンコストがあり、子があり、それぞれにコストがあります。 これらの子にはそれぞれ子があり、その結果、深さでノードが作成され、それぞれにコストがかかります。 一般に、深さにはノードがあり、それぞれにコストがかかります。

深さでのすべてのノードのコストはです。 したがって、すべての内部ノードの合計コストは次のようになります。

   

前に見たように、リーフノードの総コストはです。 したがって、合計実行時間は次の式で与えられます。

   

5. 結論

この記事では、マスター定理を実際に使用してアルゴリズムの実行時間を計算する方法を学びました。 再発を考えると、マスター定理の核心は。と比較することです。

さらに、マスター定理は、より多項式的に小さいか多項式的に大きい場合にのみ適用されます。 一方の関数がもう一方の関数より漸近的に大きい病理学的例を作成することはそれほど難しくありませんが、多項式的に大きくはありません。