Divide and conquer algorithm: Encyclopedia II - Divide and conquer algorithm - Advantages

Divide and conquer algorithm - Advantages

Divide and conquer algorithm - Solving difficult problems

Divide and conquer is a powerful tool for solving conceptually difficult problems, such as the classic Tower of Hanoi puzzle: all it requires is a way of breaking the problem into sub-problems, of solving the trivial cases and of combining sub-problems to the original problem. Dividing the problem into sub-problems so that the sub-problems can be combined again is often the major difficulty in designing a new algorithm. Indeed, for many such problems the paradigm offers the only simple solution.

Divide and conquer algorithm - Algorithm efficiency

Moreover, divide and conquer often provides a natural way to design efficient algorithms.

For example, if the work of splitting the problem and combining the partial solutions is proportional to the problem's size n, there are a bounded number p of subproblems of size ~ n/p at each stage, and the base cases require O(1) (constant-bounded) time, then the divide-and-conquer algorithm will have O(n log n) complexity. This is used for problems such as sorting and FFTs to reduce the complexity from O(n²), although in general there may also be other approaches to designing efficient algorithms.

Divide and conquer algorithm - Parallelism

Divide and conquer algorithms are naturally adapted for execution in multi-processor machines, especially shared-memory systems where the communication of data between processors does not need to be planned in advance, because distinct sub-problems can be executed on different processors.

Divide and conquer algorithm - Memory access

Divide-and-conquer algorithms naturally tend to make efficient use of memory caches. The reason is that once a sub-problem is small enough, it and all its sub-problems can, in principle, be solved within the cache, without accessing the slower main memory. An algorithm designed to exploit the cache in this way is called cache oblivious, because it does not contain the cache size(s) as an explicit parameter.

Moreover, D&C algorithms can be designed for many important algorithms, such as sorting, FFTs, and matrix multiplication, in such a way as to be optimal cache oblivious algorithms—they use the cache in a provably optimal way, in an asymptotic sense, regardless of the cache size. In contrast, the traditional approach to exploiting the cache is blocking, where the problem is explicitly divided into chunks of the appropriate size—this can also use the cache optimally, but only when the algorithm is tuned for the specific cache size(s) of a particular machine.

The same advantage exists with regards to other hierarchical storage systems, such as NUMA or virtual memory, as well as for multiple levels of cache: once a sub-problem is small enough, it can be solved within a given level of the hierarchy, without accessing the higher (slower) levels.

However, the kind of asymptotic optimality described here, analogous to big O notation, ignores constant factors, and additional machine/cache-specific tuning is in general required to achieve optimality in an absolute sense.

Adapted from the Wikipedia article "Advantages", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki