1. 序章


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


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








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


2.1. マスター定理


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


      


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


3. Akra-Bazziメソッド


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


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


      


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


3.1. Akra-Bazziの定理


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


 (1)    


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


    

  1.  十分に大きいので、明確に定義されています
    2. 

  2. それぞれについて：

      

    1. 定数 
      2. 

    2. 定数 
      3. 

    3. 

    

    3. 

  3.  定数です
    4. 

  4.  は非負の多項式成長関数です
    5. 



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


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


 (2)    




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


 (3)    


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


      


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


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


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


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


3.3. 床と天井


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


      


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


      


3.4. 境界条件


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


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


      


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


3.5. 計算について 


最後に、式（ 2 ）から、正確かつ手動で計算するのは簡単ではない場合があります。 その場合、その値を数値で概算できます。 たとえば、ニュートン法を使用できます。


ただし、計算または概算すると、常に存在し、一意です。 の条件は、関数が範囲で連続であることを確認します。 中間値の定理により、は常に解を持ち、関数も厳密に単調であるため、その解は一意になります。


3.6. 多項式のAkra-Bazzi定理 


場合によっては、定積分を評価せずに複雑さを直接導出できます。 この方法は、Akra-Bazziの定理の結果です。


バインドできる場合は、


 (4)    


幸いなことに、当然の結果は多くのアルゴリズムに適用されます。ほとんどの場合、次の形式になります。


 (5)    


ここで、最高次の係数は厳密に正になります。 理由を理解するために、それが否定的であると想像してみましょう。 その場合、は十分に大きい場合は負になりますが、これは、負のステップ数を作成することを意味するため、不可能です。


3.7. およびバージョン


一般に、の場合、ここで、次のようになります。


      


およびケースは、私たちにとって特に興味深いものです。 正確に決定することはできませんが、下（）または上（）から漸近的に制限できる場合は、の下限と上限を取得できます。


4. 例


例を考えてみましょう：


      


再発はAkra-Bazzi定理のすべての条件を満たしていることがわかります。 したがって、最初のステップはを見つけることです。


4.1. 見つける 


、、、および、なので、次のように解決する必要があります。


      


なので、方程式は次のようになります。


      


また：


      


：と。には2つの可能な値があります。 後者は負であり、正でなければならないため、後者を破棄できます。 したがって、次のように解くことで得られます。


      


そこから、次のようになります。


      


4.2. Akra-Bazzi定理の適用


まず、積分を計算しましょう。


      


次に、次のようになります。


      


4.3. ショートカット


多項式のショートカットを使用した場合、同じ結果が得られますか？ 以来、その程度はです。 として、これが正解であると結論付けます。


5. 結論


この記事では、Akra-Bazziメソッドを紹介しました。 これを使用して、マスター定理が失敗する複雑さの分割統治アルゴリズムを決定します。