Algorithm for sharing (divide and conquer)

What is the Divide and Conquer algorithm?

Divide and Conquer (Divide and Conquer) is an important method of designing algorithms. The idea of ​​this method is quite simple and easy to understand: When you need to solve a problem, we will proceed to divide that problem into smaller subproblems. Continue dividing until these small problems cannot be further divided, then we will solve these smallest problems and finally combine the solution of all small problems to find the solution of the lesson. original math.

Algorithm for sharing (divide and conquer) Picture 1

In general, you can understand the Divide and Conquer algorithm through the following three processes:

Process 1: Split (Divide / Break)

In this step, we divide the original problem into subproblems. Each subproblem should be part of the original problem. In general, this step uses recursive methods to split problems until it cannot be further divided. Then, subproblems are called "atomic", but they still represent some part of the original problem.

Process 2: Solve the problem (Conquer / Solve)

In this step, subproblems are solved.

Process 3: Combining solutions (Merge / Combine)

After subproblems have been solved, in this step we will combine them recursively to find solutions to the original problem.

Limitations of the sharing algorithm (Devide and Conquer)

The algorithm to divide and conquer existed two limitations, that is:

How to divide the problem logically into subproblems, because if subproblems are solved with different algorithms, it will be very complicated.

How to combine the solutions of subproblems is done.

Example algorithm for division

Here are some algorithms built on the Divide and Conquer method:

Alignment algorithm (Merge Sort)

Quick Sort (Quick Sort)

Binary Search algorithm (Binary Search)

Multiplication matrix of Strassen

According to Tutorialspoint

Previous lesson: Greedy Algorithm (Greedy Algorithm)

Next lesson: Dynamic Programming (Dynamic Programming)