Divide and Conquer: Overview
Divide and conquer
- Break up problem into several parts
- Solve each part recursively
- Combine solutions to sub-problems into overall solution
Most common usage
- Break up problem of size n into equal parts of size12nfrac{1}{2}n21n.
- Solve two parts recursively
- Combine two solutions into overall solution in linear time.
Remark
- Partition the problem into disjoint subproblems
- Each subproblem is the same type as the original problem
- A simple partition of the problem and combination of solutions to subproblems may not neat brute force.
The phrase is attributed to Julius Caesar, Philip II, king of Macedon(382-336 BC), describing his political policy.
