Let's start our description with a great example. How do you wake up every morning? I guess it's similar for all people:
- The alarm clock is ringing.
- We, like lazy people, lying on the bed until something happens (another alarm clock ringing, the end of the Twitter feed, etc.)
- We'll go to a shower.
- We'll prepare breakfast and will eat it after
- We'll go to work (University or school)
To sum up, we already have algorithms in our life. In fact, we always use divide and conquer principles in all that steps. Do you see it? No? It's not a big deal; you'll see it later.
Basic concept
In Divide and Conquer algorithms issue divides into small pieces, and then each problem is solved independently. We keep on dividing until a stage where no more division is possible. Then, those smallest problems (atomic problems or sub-problems) are solved. Finally, we'll merge all sub-problems to obtain the solution to an original problem.
Main Principles
As you can see Divide and Conquer approach has three main principles:
Divide. In this step, you need to think about how to break the problem into smaller sub-problems. Obviously, for this step, better to use a recursive approach. Result from this stage - sub-problems still represent part of the actual problem but become atomic.
Conquer. At this step, we have many smaller problems, and we'll need to solve them. Generally, at this level, the problems are considered 'solved' on their own.
Merge. At this moment, you have solved all sub-problems. Now you need to combine it to resolve the original problem. This step works recursively.
Examples
A lot of famous algorithms work using the divide and conquer approach:
- Quick and Merge Sort
- Binary Search
- Matrix multiplication
- Max subarray
- Closest pair or points
In previous, we have the example with a plan how to wake up. You can name it just morning routine and use the divide and conquer approach to resolve all sub-problems. But also, you can imagine and deep dive into sub-problems and divide them more.