分割統治法の利点は、複雑な問題を機械的な単純作業に落とし込める点と、並列処理との相性が非常に良い点にあります。分割されたそれぞれの小さな問題は、お互いに独立しているため、マルチコアのCPUや複数のコンピュータを用いて同時に並行して計算(統治)することが可能です。分割統治法を設計する際は、通常3つのステップを踏みます。1つ目は「分割(Divide)」で、問題を同じ形式のより小さなサブ問題に分割します。2つ目は「統治(Conquer)」で、サブ問題を再帰的に解決します(十分に小さければ直接解きます)。3つ目は「結合(Combine)」で、サブ問題の解を組み合わせて元の問題の解を構築します。この手法により、効率的なアルゴリズムが数多く開発され、情報科学の発展に大きく貢献しました。
試験でのポイント