Heading

divide and conquer algorithmは、大きな問題を解決するための戦略で、

1. 問題を小さなサブ問題に分解し、
2. サブ問題を解決し、
3. それらを組み合わせて目的の出力を得ることができます。

divide and conquer algorithmを使用するには、再帰が使用されます。

• Javaでの再帰
• Pythonでの再帰
• C++での再帰

How Divide and Conquer Algorithms Work?

以下のステップがあります：

1. 分割。
2. Conquer: 小さいサブ問題を再帰的に解きます。 サブプロブレムが十分小さい場合は、それを直接解きます。
3. Combine:

例を挙げてこの概念を理解しましょう。

ここでは、分割統治法 (マージ ソート) を使用して配列をソートします。

1. 与えられた配列を次のようにします：
   

   

2. 配列を2つに分割します。
   

   

   さらに、個々の要素が得られるまで、各サブパートを再帰的に2つのハーフパートに分割します。

   

3. さて、個々の要素を並べ替えて結合します。 ここでは、「征服」と「結合」のステップが並行して行われます。
   

   

   。

時間的複雑さ

分割統治アルゴリズムの複雑さは、マスターの定理を使って計算されます。

T(n) = aT(n/b) + f(n),where,n = size of inputa = number of subproblems in the recursionn/b = size of each subproblem. All subproblems are assumed to have the same size.f(n) = cost of the work done outside the recursive call, which includes the cost of dividing the problem and cost of merging the solutions

再帰的な問題の時間的複雑さを求める例を見てみましょう。

マージソートの場合、式は次のように書くことができます。

T(n) = aT(n/b) + f(n) = 2T(n/2) + O(n)Where, a = 2 (each time, a problem is divided into 2 subproblems)n/b = n/2 (size of each sub problem is half of the input)f(n) = time taken to divide the problem and merging the subproblemsT(n/2) = O(n log n) (To understand this, please refer to the master theorem.)Now, T(n) = 2T(n log n) + O(n) ≈ O(n log n)

Divide and Conquer Vs Dynamic approach

fib(n) If n < 2, return 1 Else , return f(n - 1) + f(n -2)

mem = fib(n) If n in mem: return mem else, If n < 2, f = 1 else , f = f(n - 1) + f(n -2) mem = f return f