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:
- 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.
- To rule: the sub-problems are solved recursively.
- 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.
