# Divide & conquer

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.

## Principle 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:

1. 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.
2. Rule: sub-problems are solved recursively.
3. Combine: sub-problem solutions are recommended to rebuild the solution to the initial problem.

## Example

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;
else {
if (n%2==0) return power(x*x, n/2);
else return x*power(x*x, (n-1)/2);
end if
end if
}```

Its complexity is in 0(log n) – size of the complete binary tree with n vertices.

Publicités