分割統治アルゴリズム

分割統治法は、概念的に難しい問題を解決するための強力なツールです。必要なのは、問題を部分問題に分解し、些細なケースを解決し、部分問題を元の問題に組み合わせる方法だけです。同様に、縮小統治法では、問題を単一のより小さな問題に縮小するだけで済みます。例えば、古典的なハノイの塔パズルでは、高さの塔を動かすという問題を縮小します。${\displaystyle n}$高さのある塔を移動させる${\displaystyle n-1}$。

分割統治法は、効率的なアルゴリズムの発見に役立つことが多い。例えば、カラツバの高速乗算法、クイックソートやマージソートといったアルゴリズム、行列乗算のためのシュトラッセンのアルゴリズム、そして高速フーリエ変換などが、この手法によって開発された。

これらの例すべてにおいて、D&Cアプローチは解の漸近コストの改善につながった。例えば、(a)基本ケースのサイズが一定の範囲内である場合、問題を分割して部分解を組み合わせる作業は問題のサイズに比例する。${\displaystyle n}$（b）有界数が存在する${\displaystyle p}$サイズのサブ問題 ~${\displaystyle {\frac {n}{p}}}$各段階において、分割統治アルゴリズムのコストは${\displaystyle O(n\log _{p}n)}$。

他のタイプの分割統治法についても、実行時間を一般化することができます。たとえば、a) 問題を分割して部分解を組み合わせる作業に時間がかかる場合${\displaystyle cn}$時間、${\displaystyle n}$入力サイズと${\displaystyle c}$は定数である。b) の場合${\displaystyle n<2}$アルゴリズムの実行時間は上限が${\displaystyle c}$c) は${\displaystyle q}$各部分問題のサイズが ~ である部分問題${\displaystyle {\frac {n}{2}}}$すると、実行時間は以下のようになります。

• 部分問題の数${\displaystyle q>2}$すると、分割統治アルゴリズムの実行時間は以下によって制限される。${\displaystyle O(n^{\log _{2}q})}$。
• 部分問題の数がちょうど 1 の場合、分割統治アルゴリズムの実行時間は以下によって制限されます。${\displaystyle O(n)}$[ ^{10 ]​}

代わりに、問題を分割して部分的な解決策を組み合わせる作業に${\displaystyle cn^{2}}$時間があり、それぞれサイズが 2 つのサブ問題があります${\displaystyle {\frac {n}{2}}}$すると、分割統治アルゴリズムの実行時間は以下によって制限される。${\displaystyle O(n^{2})}$[ ^{10 ]​}

分割統治アルゴリズムは、マルチプロセッサマシン、特に共有メモリシステムでの実行に自然と適しています。共有メモリシステムでは、異なるプロセッサ上で個別のサブ問題を実行できるため、プロセッサ間のデータ通信を事前に計画する必要がありません。

分割統治アルゴリズムは、メモリ キャッシュを効率的に利用する傾向があります。その理由は、部分問題が十分に小さくなれば、原則として、その部分問題とすべての部分問題を、より遅いメイン メモリにアクセスすることなく、キャッシュ内で解決できるからです。このようにキャッシュを活用するように設計されたアルゴリズムは、キャッシュ サイズを明示的なパラメータとして含まないため、キャッシュ非依存アルゴリズムと呼ばれます。^{[ 11 ]}さらに、重要なアルゴリズム (ソート、FFT、行列乗算など) に対して、D&C アルゴリズムを最適なキャッシュ非依存アルゴリズムとして設計することができます。つまり、キャッシュ サイズに関係なく、漸近的に、おそらく最適な方法でキャッシュを使用します。対照的に、キャッシュを活用する従来のアプローチは、ループ ネスト最適化のように、問題を適切なサイズのチャンクに明示的に分割するブロッキングです。これもキャッシュを最適に使用できますが、特定のマシンの特定のキャッシュ サイズに合わせてアルゴリズムが調整されている場合に限ります。

NUMAや仮想メモリなどの他の階層型ストレージシステム、および複数レベルのキャッシュについても同様の利点があります。つまり、サブ問題が十分に小さければ、上位（低速な）レベルにアクセスすることなく、階層内の特定のレベル内で解決できるということです。

丸め演算、例えば浮動小数点数を用いた計算では、分割統治アルゴリズムの方が、一見同等の反復法よりも正確な結果が得られる場合があります。例えば、N 個の数値を加算するには、各データを単一の変数に加算する単純なループを用いる方法と、データセットを 2 つの半分に分割し、それぞれの半分の合計を再帰的に計算し、その 2 つの合計を加算するペアワイズ加算と呼ばれる分割統治アルゴリズムを用いる方法があります。後者の方法は前者と同じ回数の加算を行い、再帰呼び出しのオーバーヘッドが発生しますが、通常はより正確です。^{[ 12 ]}

分割統治アルゴリズムは、本質的に再帰的な手続きとして実装されます。その場合、現在解決中の問題につながる部分的なサブ問題は、手続き呼び出しスタックに自動的に格納されます。再帰関数とは、定義内で自身を呼び出す関数のことです。

分割統治アルゴリズムは、部分的なサブ問題をスタック、キュー、優先度付きキューなどの明示的なデータ構造に格納する非再帰的なプログラムによって実装することもできます。このアプローチでは、次に解決するサブ問題の選択に自由度が高まります。これは、幅優先探索や関数最適化のための分岐限定法など、一部のアプリケーションで重要な機能です。また、このアプローチは、再帰的な手続きをサポートしていないプログラミング言語における標準的な解決策でもあります。

D&Cアルゴリズムの再帰実装では、再帰スタックに十分なメモリが割り当てられていることを確認する必要があります。そうでない場合、スタックオーバーフローにより実行が失敗する可能性があります。時間効率の良いD&Cアルゴリズムは、再帰の深さが比較的小さいことが多いです。たとえば、クイックソートアルゴリズムは、再帰の深さが常に 100 を超える必要がないように実装できます。${\displaystyle \log _{2}n}$ネストされた再帰呼び出しでソートする${\displaystyle n}$アイテム。

再帰処理を使用する場合、スタックオーバーフローを防ぐのは困難です。多くのコンパイラは再帰スタックを連続したメモリブロックとして扱い、中にはスタック用に一定量の領域を確保するものもあるためです。さらに、コンパイラは、戻りアドレス、変更されないパラメータ、プロシージャのローカル変数など、厳密には必要以上の情報を再帰スタックに格納する場合があります。そのため、再帰処理におけるパラメータとローカル変数の数を制限するか、再帰を明示的なスタックデータ構造に置き換えることで、スタックオーバーフローの発生確率を低減できます。

再帰アルゴリズムにおいては、再帰を終了させるために直接解決される小さな部分問題である基本ケースの選択にかなりの自由度がある。

可能な限り最小または最も単純な基本ケースを選択する方が、より洗練されており、考慮すべきケースが少なくなり、解決が容易になるため、通常はよりシンプルなプログラムにつながります。たとえば、高速フーリエ変換アルゴリズムは、入力が単一のサンプルである場合に再帰を停止できます。また、クイックソートリストソートアルゴリズムは、入力が空のリストである場合に停止できます。どちらの例でも、考慮すべき基本ケースは1つだけであり、処理は必要ありません。

一方、比較的大きな基本ケースで再帰を停止し、それらを非再帰的に解決することで、ハイブリッド アルゴリズムが実現され、効率が向上することがよくあります。この戦略は、ほとんどまたは全く作業を行わない再帰呼び出しのオーバーヘッドを回避し、また、それらの基本ケースに対して明示的な再帰よりも効率的な特殊な非再帰アルゴリズムの使用も可能にします。単純なハイブリッド再帰アルゴリズムの一般的な手順は、基本ケースの短絡、別名アームズ レングス再帰です。この場合、次のステップが基本ケースになるかどうかは関数呼び出しの前にチェックされ、不要な関数呼び出しが回避されます。たとえば、ツリーでは、子ノードに再帰してからそれが null かどうかをチェックするのではなく、再帰の前に null をチェックすることで、二分木上の一部のアルゴリズムで関数呼び出しの半分を回避できます。 D&Cアルゴリズムは最終的に各問題または部分問題のインスタンスを多数の基本インスタンスに縮小するため、特に分割/結合のオーバーヘッドが低い場合、これらの基本インスタンスがアルゴリズム全体のコストの大部分を占めることがよくあります。なお、これらの考慮事項は、再帰がコンパイラによって実装されているか、明示的なスタックによって実装されているかには依存しません。

したがって、たとえば、クイックソートの多くのライブラリ実装は、ソートする項目の数が十分に小さくなると、単純なループベースの挿入ソート（または類似の）アルゴリズムに切り替わります。空のリストが唯一の基本ケースである場合、リストをソートするには、${\displaystyle n}$エントリーには最大で${\displaystyle n}$ quicksort calls that would do nothing but return immediately. Increasing the base cases to lists of size 2 or less will eliminate most of those do-nothing calls, and more generally a base case larger than 2 is typically used to reduce the fraction of time spent in function-call overhead or stack manipulation.

Alternatively, one can employ large base cases that still use a divide-and-conquer algorithm, but implement the algorithm for predetermined set of fixed sizes where the algorithm can be completely unrolled into code that has no recursion, loops, or conditionals (related to the technique of partial evaluation). For example, this approach is used in some efficient FFT implementations, where the base cases are unrolled implementations of divide-and-conquer FFT algorithms for a set of fixed sizes.^[13]Source-code generation methods may be used to produce the large number of separate base cases desirable to implement this strategy efficiently.^[13]

The generalized version of this idea is known as recursion "unrolling" or "coarsening", and various techniques have been proposed for automating the procedure of enlarging the base case.^[14]

For some problems, the branched recursion may end up evaluating the same sub-problem many times over. In such cases it may be worth identifying and saving the solutions to these overlapping subproblems, a technique which is commonly known as memoization. Followed to the limit, it leads to bottom-up divide-and-conquer algorithms such as dynamic programming.