Akra-Bazziメソッド - 開発者ドキュメント

1. 序章

このチュートリアルでは、Akra-Bazziメソッドを紹介します。これは、分割統治アルゴリズムの複雑さのクラスを決定するために使用する定理です。

2. 分割統治アルゴリズムの複雑さ

分割統治法は、問題をより小さなサブ問題に分割し、それらのソリューションを組み合わせることによって問題を解決するアルゴリズム設計手法です。各サブ問題は同じように扱われます。つまり、問題をより小さな部分に分割します。、それらを再帰的に解決し、サブソリューションを統合します。

2.1. マスター定理

サブ問題が同じサイズの場合は、マスター定理を使用します。これらは、サイズの問題を解決する際にアルゴリズムが行うステップ数が次の形式の繰り返しであるものです。

ここで、は実数値関数です。より具体的には、再発は、サイズの問題を各サイズのサブ問題に分割するアルゴリズムの複雑さを表します。問題を分解し、そのサブ問題の解決策を組み合わせるための手順を実行します。

3. Akra-Bazziメソッド

マスター定理を使用して、多くのアルゴリズムの複雑さを判断できます。たとえば、これを使用して、マージソートが対数線形の最悪の場合の複雑さを持っていることを示すことができます。残念ながら、マスター定理が常に適用できるとは限りません。

再発が次のようになっているとしましょう。

つまり、サイズの問題をサイズのサブ問題に分割し、それらのソリューションを組み合わせる手順を実行します。 サブ問題が不均一であるため、マスター定理を使用できません。

3.1. Akra-Bazziの定理

代わりに、より一般的な Akra-BazziTheoremを使用します。次のフォームの繰り返しに適用できます。

(1)

ここで、は有界であり、次のことが成り立ちます。

十分に大きいので、明確に定義されています
それぞれについて：
1. 定数
2. 定数
定数です
は非負の多項式成長関数です

すべてのに対して、が存在する場合、それは多項式成長条件を満たすと言います。この条件により、変化が速すぎないことが保証されます。が多項式で囲まれている場合に成立します。

条件1〜4が満たされ、方程式の一意の実数解である場合：

(2)

次に、Akra-Bazziの定理は次のことを保証します。

(3)

保持するには追加の技術的条件が必要であることに注意してください。 式（3）の積分は有限である必要があります：

3.2. アルゴリズム分析のコンテキストにおけるAkra-Bazziの定理

この定理は、実数と一般的な繰り返しに当てはまります。ただし、複雑さの分析では、特定の種類の反復関数を扱います。

まず、は正の整数にのみ適用されるため、このアプリケーションでは。これは、入力サイズが整数であるためです。

の値は、サイズの入力をより小さなサブ問題に分割し、それらを再帰的に解決した後にそれらのソリューションを組み合わせるためにアルゴリズムが実行するステップ数を表します。さらに、入力の処理に追加の作業が必要になる場合があります。それをアルゴリズムの実装に渡すことは、少なくとも1ステップとしてカウントされるため、は厳密に正になります。同じ理由で、は常に正のになります。

3.3. 床と天井

はアルゴリズムの分析では整数であるため、の代わりにまたはを使用する必要があります。幸いなことに、漸近的成長に影響を与えないため、天井関数と床関数は無視できます。それが関数の目的です。回避するために、用語を次のように設定して書き直します。

そのため、通常、実際にはsを使用せずに繰り返しを定式化します。それでも正しい結果が得られますが、より単純な式で作業します。

3.4. 境界条件

定理の結果を詳しく見ると、そこには表示されていないことがわかります。それは最初はやや直感に反しているように見えるかもしれません。結局のところ、基本ケースのすべての値を2倍にすると、の最終値はすべてのに対して2倍になると予想されます。ただし、基本ケースをスケーリングすると、関数に定数が乗算されるだけであり、乗法定数は漸近的動作に影響を与えません。同様に、これは、アルゴリズムの漸近的振る舞いがその基本ケースから独立していることを意味します。

また、それが明確に定義されるように、十分な大きさである必要があるとも言います。理由を確認するために、を考えてみましょう。の場合、再帰的に解きます。

これは矛盾です。したがって、は、このようなすべてのケースに対応できる十分な大きさである必要があります。