Divide and conquer algorithms

In computer science, parts designated and conquer (English divide and conquer or Latin divide et impera ) is a paradigm for the design of efficient algorithms.

Basic principle

With a " divide and conquer " approach is the real problem as long recursively decomposed into smaller and simpler sub-problems, until one ( "control" ) can solve this. Is then constructed from these partial solutions a solution to the overall problem ( re-).

Historical antecedents

The binary search for a key is one of the first algorithmic applications of the principle of " divide and rule ". They can be traced back to the Babylonians. In binary search key is searched in a sorted set of keys. Comparing to this key with the median of the set of keys, and then searches in the corresponding subset of the elements is less than the median, or the subset of the elements are larger than the median recursively.

The Euclidean algorithm for finding the greatest common divisor of two numbers also follows the " divide-and- conquer" principle. Here the problem is iteratively simplified by " common " parts removed.

Application in algorithms

" Divide and conquer " is one of the most important principles for efficient algorithms. This exploits that for many problems the solution effort is reduced if one divides the problem into smaller sub-problems. This can be implemented mostly by Recursive programming in which the subproblems as independent problems are treated simultaneously in parallel or sequentially ( one at a time ) until they are reduced to trivial solutions or the residual error is sufficiently small. For some algorithms it puts the core idea in the step of " sharing ", while the " recombination " is simple (eg, quicksort ). In other methods ( for example, mergesort ) sharing is simple, while the recombination contains the core idea of the algorithm. In some algorithms, both steps are complex.

The solution to the overall problem arises depending on the algorithm in different ways. Ways, among others:

• The partial solutions are combined into an overall solution. For example, the list of results is composed of small, stocked separately, are part of lists by the juxtaposition of the sort with the Quicksort algorithm.
• The partial solutions are combined into an overall solution. For example, when sorting with the mergesort algorithm, the result of two sorted parts by the "Merge " is constructed step.
• From the partial solutions, the best solution is selected as the solution to the overall problem according to certain criteria. For example, in some optimization problems, the solution space is divided up and wanted out of the subspaces the optimal solution. From the " subspace Optima" the best solution is then selected as the overall solution. Specifically, as Krylov subspace methods.
• The solution for the last part of the problem is the same solution of the whole problem. For example, the appropriate authority is designated in the tree when searching in the binary tree after the last search step.
• Another important application is the Fast Fourier Transform (FFT).

Application in programming languages

In many programming languages, the structure of computer programs in procedures, functions, modules, objects, components, processes and threads will share the principle and rule implemented.