Divide-and-conquer

The divide and conquer method ( English divide and conquer or Latin divide et impera ) describes a paradigm in computer science for the design of efficient algorithms .

The principle is used, among other things, in search and sorting processes .

Basic principle

With a divide-and-conquer approach, the actual problem - in its entirety - that appears to be too difficult is recursively broken down into smaller and simpler sub-problems until these are solved (“manageable”). A solution for the overall problem is then (re) constructed from these partial solutions.

Historical precursors

The binary search for a key is one of the first algorithmic applications of the principle of “divide and rule”. It can be traced back to the Babylonians . In the binary search, a key is searched for in a sorted set of keys. To do this, one compares the key sought with the median of the key set and then searches recursively in the subset of elements smaller than the median or in the subset of elements larger than the median.

The Euclidean algorithm for determining the greatest common divisor of two numbers also follows the “divide-and-conquer” principle. This iteratively simplifies the problem by removing “common” parts.

Application in algorithms

“Divide and conquer” is one of the most important principles for efficient algorithms . This makes use of the fact that the solution effort for many problems is reduced if the problem is broken down into smaller sub-problems. This can usually be implemented through recursive programming , in which the sub-problems are treated as independent problems at the same time in parallel or sequentially (one after the other) until they are reduced to trivial solutions or the residual error is sufficiently small. With some algorithms, the core idea lies in the “dividing” step, while “recombining” is simple (for example, Quicksort ). In other methods (such as mergesort ) splitting is simple, while recombination contains the core idea of the algorithm. In some algorithms, both steps are complex.

The solution to the overall problem arises in different ways depending on the algorithm. Options include:

The partial solutions are combined to form an overall solution. For example, when sorting with the quicksort algorithm, the sorted result list is composed of small, individually sorted sublists by stringing them together.

The partial solutions are combined to form an overall solution. For example, when sorting with the merge sort algorithm, the result is constructed from two sorted parts by the “merge” step.

The best solution for the overall problem is selected from the partial solutions according to certain criteria. For example, the solution space is divided up for some optimization problems and the optimal solution is sought from the sub-spaces . The best solution is then selected as an overall solution from the “sub-room optima”. Specifically, for example, the Krylow subspace method .

The solution to the last sub-problem is also the solution to the whole problem. For example, when searching in the binary tree, the right place in the tree is determined after the last search step.

Another important area of application is the Fast Fourier Transform (FFT).

Application in programming languages

In many programming languages , the division of computer programs into procedures , functions , modules , objects , components , processes and threads is implemented according to the principle of divide and rule.

Application beyond computer science

The “divide and conquer” method can also be used for problems in non-mathematical subjects and in everyday life. A difficult problem is broken down into small sub-problems, which can then be solved individually and combined to form an overall result. For example, if you want to write a book, you can write a sketch as a framework, then approach each component individually and finally put everything together to form a coherent work.

Individual evidence

^ Charles Fadel, Bernie Trilling, Maya Bialik: Four-Dimensional Education: The Competencies Learners Need to Succeed. 2015, ISBN 978-1518642562 , p. 79.

[1] Charles Fadel, Bernie Trilling, Maya Bialik: Four-Dimensional Education: The Competencies Learners Need to Succeed. 2015, ISBN 978-1518642562 , p. 79.