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)

Marvin Fry

Update 25 May 2019

You should read it

May be interested

What is Data Structure?
data structure is a way of storing, organized and systematic data organization so that data can be used effectively.
Environment settings in Data structures
because c and c ++ languages are the languages that almost every university uses to teach, in this chapter i will guide you to install c and c ++ to run the examples in the configuration series. structure and algorithm.
Array data structure
array (array) is one of the oldest and most important data structures. arrays can store some fixed elements and these elements have the same type. most data structures use arrays to implement algorithms. here are the important concepts related to arrays.
What is algorithm?
algorithms (also known as algorithms - english is algorithms) is a finite set of instructions to be executed in a certain order to get the desired result. in general, the algorithm is independent of programming languages, ie an algorithm can be deployed in many different programming languages.
Asymptotic analysis in Data Structures and Algorithms
the asymptotic analysis of an algorithm is a concept that helps us estimate the running time of an algorithm. using asymptotic analysis, we can draw the best conclusions about the best case scenario, the average case, the worst case of an algorithm.
Greedy Algorithm (Greedy Algorithm)
greedy algorithm is a combination optimization algorithm. search algorithms, select local optimal solutions in each step in the hope of finding a global optimal solution.