Authored by Tony Feng
Created on April 3rd, 2022
Last Modified on April 3rd, 2022
Understanding Divide & Conquer
Intro
- In computer science, divide and conquer is an algorithm design paradigm.
- A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.
Components
- Divide/Break
- This involves dividing the problem into smaller sub-problems.
- Conquer/Solve
- Solve sub-problems by calling recursively until solved.
- Combine/Merge
- Combine the sub-problems to get the final solution of the whole problem.
Applications
- Merge Sort
- Quick Sort
- Binary Search
- Strassen’s Matrix Multiplication
- Closest pair (points)
Examples
Tower of Hanoi
|
|
Merge Sort
|
|
Reference
- 手把手带你刷Leetcode力扣 - 分治法 Divide & Conquer
- Programiz - Divide & Conquer
- GreekforGreek - Merge Sort
- GreekforGreek - Python Program for Tower of Hanoi