10/08/2024

# Divide and rule

Contents

Toggle

## Divide and rule

The divide and conquer method is a method that sometimes makes it possible to find effective solutions to algorithmic problems. The idea is to cut out the initial problem, size not, into several sub-problems of smaller size, then to recombine the partial solutions until obtaining the final solution.

## Principle

Unlike the dynamic programming, the results of the sub-problems are only useful for the result of the parent problem.

The divide and conquer algorithm is broken down into three steps:

1. Divide: the problem is split into size sub-problems b / w. These sub-problems are of the same nature as their parent. We are therefore in the presence of To identical subproblems. When b = 2, we are talking about dichotomy.
2. To rule: the sub-problems are solved recursively.
3. Recombine: the solutions of the subproblems are recombined to reconstruct the solution to the initial problem.

## Example

In order to better understand the construction of the algorithm, we will take the example of fast exponentiation. The principle of this algorithm is to calculate xnot.

A naive method would be to loop where a*= x with a = 1 initially. The complexity of the naive method is therefore 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 subproblems. Since this is a recursive method, don't forget to include an end state. We are therefore in the presence of the following mathematical program:

The algorithm is as follows:

```double power (double x, int n) {
yew (n == 0) return 1;
else {
yew (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 at not tops.