The method of divide and conquer is a method that allows to find effective solutions to algorithmic problems. The idea is to cut the initial problem, of size n, into several sub-problems of smaller size, then to recombine the partial solutions until the final solution.
Unlike dynamic programming, sub-problem results are only useful for the outcome of the parent problem.
The divide and conquer algorithm breaks down into three stages:
- Divide: the problem is broken down into b sub-problems of size n/b. These sub-problems are of the same nature as their parent. We are in the presence of identical subproblems. When b = 2, we are talking about dichotomy.
- Rule: sub-problems are solved recursively.
- Combine: sub-problem solutions are recommended to rebuild the solution to the initial problem.
In order to better understand the construction of the algorithm, we will take the example of rapid exponentiation. The principle of this algorithm is to calculate xn.
A naive method would be to make a loop where a*=x with a=1 initially. The complexity of the naive method is linear 0(n).
In order to use the divide and conquer method, we need to find a mathematical program to rewrite our problem into equivalent sub-problems. Since this is a recursive method, do not forget to include a final state. We are therefore in the presence of the following mathematical program:
Traduction of french words: Initial/If n is even/Otherwise
The algorithm is as follows:
double power(double x, int n)
if (n==0) return 1;
if (n%2==0) return power(x*x, n/2);
else return x*power(x*x, (n-1)/2);
Its complexity is in 0(log n) – size of the complete binary tree with n vertices.