分割および征服アルゴリズムの漸近的な複雑さは、マスター定理を使用して推定できます。マスター定理は、分割および征服の実行時間を分析する方法を提供します。アルゴリズムは、問題をサブ問題に分割することで問題を解決し、サブ問題を再帰的に解決し、サブ問題のソリューションを組み合わせて元の問題を解決することで解決するアルゴリズムです。

マスター定理は、分裂と征服アルゴリズムがフォームの再発関係の形をとる場合、次のように述べています。

t（n）= at（n/b） + f（n）

ここで、nは問題のサイズです。aはサブ問題の数、bはサブ問題のサイズが縮小される要因であり、f（n）は問題を分割し、ソリューションを結合するコストを表す関数です、次に、アルゴリズムの漸近的な複雑さが次のように与えられます。

t（n）= o（n^d log n）a = b^dの場合は、一定のd> 0およびf（n）= o（n^（d-1）log n）の場合
t（n）= o（n^d）a = b^dの場合は、d> 0とf（n）= o（n^d）の場合
t（n）= o（n^log_b a）定数d> 0およびf（n）= o（n^（log_b a -1）の場合はa> b^dの場合）
t（n）= o（f（n））定数d> 0の場合はa <b^dの場合。

アルゴリズムの漸近的な複雑さは、サブ問題のサイズと問題を分割し、ソリューションを組み合わせるコストがどのように互いに関連するかに依存します。マスター定理を分裂と征服アルゴリズムの再発関係に適用することにより、その漸近的な複雑さを判断し、問題のサイズが増加するにつれてアルゴリズムの実行時間がどのように成長するかについて良い考えを得ることができます。
The asymptotic complexity of divide and conquer algorithms can be estimated using the master theorem. The master theorem provides a way to analyze the running time of divide and conquer algorithms, which are algorithms that solve a problem by dividing it into subproblems, solving the subproblems recursively, and then combining the solutions of the subproblems to solve the original problem.

The master theorem states that if a divide and conquer algorithm takes the form of a recurrence relation of the form:

T(n) = aT(n/b) + f(n)

where n is the size of the problem, a is the number of subproblems, b is the factor by which the size of the subproblems is reduced, and f(n) is a function that represents the cost of dividing the problem and combining the solutions, then the asymptotic complexity of the algorithm is given by:

T(n) = O(n^d log n) if a = b^d for some constant d > 0 and f(n) = O(n^(d-1) log n)
T(n) = O(n^d) if a = b^d for some constant d > 0 and f(n) = O(n^d)
T(n) = O(n^log_b a) if a > b^d for any constant d > 0 and f(n) = O(n^(log_b a - 1))
T(n) = O(f(n)) if a < b^d for any constant d > 0.

The asymptotic complexity of the algorithm depends on how the size of the subproblems and the cost of dividing the problem and combining the solutions relate to each other. By applying the master theorem to the recurrence relation of the divide and conquer algorithm, you can determine its asymptotic complexity and get a good idea of how the running time of the algorithm grows as the size of the problem increases.