In
computer scienceComputer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems. It is frequently described as the systematic study of algorithmic processes that create, describe and transform...
,
divide and conquer (
D&C) is an important
algorithm designAlgorithm design is a specific method to create a mathematical process in solving problems. Applied algorithm design is algorithm engineering....
paradigmThe word paradigm has been used in linguistics and science to describe distinct concepts....
based on multi-branched
recursionRecursion, in mathematics and computer science, is a method of defining functions in which the function being defined is applied within its own definition. The term is also used more generally to describe a process of repeating objects in a self-similar way...
. A divide and conquer
algorithmIn mathematics, computing, linguistics, and related subjects, an algorithm is an effective method for solving a problem using a finite sequence of instructions. Algorithms are used for calculation, data processing, and many other fields....
works by recursively breaking down a problem into two or more sub-problems of the same (or related) type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.
This technique is the basis of efficient algorithms for all kinds of problems, such as
sortingIn computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...
(e.g.,
quicksortQuicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, on average, makes comparisons to sort n items. However, in the worst case, it makes comparisons...
,
merge sortMerge sort is an O comparison-based sorting algorithm. In most implementations it is stable, meaning that it preserves the input order of equal elements in the sorted output. It is an example of the divide and conquer algorithmic paradigm...
),
multiplying large numbersA multiplication algorithm is an algorithm to multiply two numbers. Depending on the size of the numbers, different algorithms are in use...
(e.g.
KaratsubaThe Karatsuba algorithm is an efficient procedure for multiplying large numbers that was discovered by Anatolii Alexeevitch Karatsuba in 1960 and published in 1962. It reduces the multiplication of two n-digit numbers to at most single-digit multiplications in general...
), syntactic analysis (e.g., top-down parsers), and computing the
discrete Fourier transformIn mathematics, the discrete Fourier transform is a specific kind of Fourier transform, used in Fourier analysis. It transforms one function into another, which is called the frequency domain representation, or simply the DFT, of the original function...
(
FFTA fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. There are many distinct FFT algorithms involving a wide range of mathematics, from simple complex-number arithmetic to group theory and number theory; this article gives an overview of...
s).
On the other hand, the ability to understand and design D&C algorithms is a skill that takes time to master. As when proving a
theoremIn mathematics, a theorem is a statement proved on the basis of previously accepted or established statements such as axioms. In formal mathematical logic, the concept of a theorem may be taken to mean a formula that can be derived according to the derivation rules of a fixed formal system.In...
by induction, it is often necessary to replace the original problem by a more general or complicated problem in order to get the recursion going, and there is no systematic method for finding the proper generalization.
The name "divide and conquer" is sometimes applied also to algorithms that reduce each problem to only one subproblem, such as the binary search algorithm for finding a record in a sorted list (or its analog in numerical computing, the bisection algorithm for
root findingA root-finding algorithm is a numerical method, or algorithm, for finding a value x such that f = 0, for a given function f. Such an x is called a root of the function f....
) . These algorithms can be implemented more efficiently than general divide-and-conquer algorithms; in particular, if they use
tail recursionIn computer science, tail recursion is a special case of recursion in which the last operation of the function, the tail call, is a recursive call. Such recursions can be easily transformed to iterations. Replacing recursion with iteration, manually or automatically, can drastically decrease the...
, they can be converted into simple loops. Under this broad definition, however, every algorithm that uses recursion or loops could be regarded as a "divide and conquer algorithm". Therefore, some authors consider that the name "divide and conquer" should be used only when each problem may generate two or more subproblems. The name
decrease and conquer has been proposed instead for the single-subproblem class.
The correctness of a divide and conquer algorithm is usually proved by
mathematical inductionMathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers. It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite...
, and its computational cost is often determined by solving
recurrence relationIn mathematics, a recurrence relation is an equation that defines a sequence recursively: each term of the sequence is defined as a function of the preceding terms.A difference equation is a specific type of recurrence relation....
s.
Early historical examples
Binary search, a divide and conquer algorithm in which the original problem is successively broken down into
single subproblems of roughly half the original size, has a long history. The idea of using a sorted list of items to facilitate searching dates back as far as Babylonia in 200BC, while a clear description of the algorithm on computers appeared in 1946 in an article by John Mauchly. Another divide and conquer algorithm with a single subproblem is the
Euclidean algorithmIn mathematics, the Euclidean algorithm is an efficient method for computing the greatest common divisor , also known as the greatest common factor or highest common factor...
to compute the
greatest common divisorIn mathematics, the greatest common divisor , also known as the greatest common factor , the greatest common denominator, or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.This notion can be extended to...
of two numbers (by reducing the numbers to smaller and smaller equivalent subproblems), which dates to several centuries BC.
An early example of a divide-and-conquer algorithm with multiple subproblems is
GaussJohann Carl Friedrich Gauss was a German mathematician and scientist who contributed significantly to many fields, including number theory, statistics, analysis, differential geometry, geodesy, geophysics, electrostatics, astronomy and optics...
's 1805 description of what is now called the
Cooley-Tukey fast Fourier transformThe Cooley-Tukey algorithm, named after J.W. Cooley and John Tukey, is the most common fast Fourier transform algorithm. It re-expresses the discrete Fourier transform of an arbitrary composite size N = N1N2 in terms of smaller DFTs of sizes N1 and N2,...
(FFT) algorithm, although he did not analyze its operation count quantitatively and FFTs did not become widespread until they were rediscovered over a century later.
An early two-subproblem D&C algorithm that was specifically developed for computers and properly analyzed is the
merge sortMerge sort is an O comparison-based sorting algorithm. In most implementations it is stable, meaning that it preserves the input order of equal elements in the sorted output. It is an example of the divide and conquer algorithmic paradigm...
algorithm, invented by
John von NeumannJohn von Neumann was a Hungarian American mathematician who made major contributions to a vast range of fields, including set theory, functional analysis, quantum mechanics, ergodic theory, continuous geometry, economics and game theory, computer science, numerical analysis, hydrodynamics John...
in 1945.
Another notable example is the
algorithmThe Karatsuba algorithm is an efficient procedure for multiplying large numbers that was discovered by Anatolii Alexeevitch Karatsuba in 1960 and published in 1962. It reduces the multiplication of two n-digit numbers to at most single-digit multiplications in general...
invented by
A. KaratsubaAnatolii Alexeevitch Karatsuba is a Russian mathematician, best known for the Karatsuba algorithm, a fast procedure for multiplying large numbers.-Professional life:...
in 1960 that could multiply two
n-digit numbers in operations. This algorithm disproved
Andrey KolmogorovAndrey Nikolaevich Kolmogorov was a Soviet Russian mathematician, preeminent in the 20th century, who advanced various scientific fields .-Early life:Kolmogorov was born at Tambov in 1903...
's 1956 conjecture that operations would be required for that task.
As another example of a divide and conquer algorithm that did not originally involve computers,
KnuthDonald Ervin Knuth is a renowned computer scientist and Professor Emeritus of the Art of Computer Programming at Stanford University....
gives the method a
post officeA post office is a facility authorised by a postal system for the posting, receipt, sorting, handling, transmission or delivery of mail. Post offices offer mail-related services such as post office boxes, postage and packaging supplies...
typically uses to route mail: letters are sorted into separate bags for different geographical areas, each of these bags is itself sorted into batches for smaller sub-regions, and so on until they are delivered. This is related to a
radix sortIn computer science, radix sort is a sorting algorithm that sorts integers by processing individual digits, by comparing individual digits sharing the same significant position. A positional notation is required, but because integers can represent strings of characters and specially formatted...
, described for
punch-card sortingCard Sorters in the IBM 80 series were:*IBM 80 Electric Punched Card Sorting Machine Introduced by IBM in 1925. This sorter was almost twice the speed of the older Hollerith 70 vertical sorter and used an entirely new magnetically operated horizontal sorting design...
machines as early as 1929.
Solving difficult problems
Divide and conquer is a powerful tool for solving conceptually difficult problems, such as the classic
Tower of HanoiThe Tower of Hanoi or Towers of Hanoi is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod...
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.
Algorithm efficiency
The divide-and-conquer paradigm often helps in the discovery of efficient algorithms. It was the key, for example, to Karatsuba's fast multiplication method, the quicksort and mergesort algorithms, and fast Fourier transforms.
In all these examples, the D&C approach led to an improvement in the asymptotic cost of the solution.
For example, if the base cases have constant-bounded size, the work of splitting the problem and combining the partial solutions is proportional to the problem's size
n, and there are a bounded number
p of subproblems of size ~
n/
p at each stage, then the cost of the divide-and-conquer algorithm will be O(
n log
n).
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.
Memory access
Divide-and-conquer algorithms naturally tend to make efficient use of memory
cacheIn computer science, a cache is a collection of data duplicating original values stored elsewhere or computed earlier, where the original data is expensive to fetch or to compute, compared to the cost of reading the cache. In other words, a cache is a temporary storage area where frequently...
s. 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
NUMANon-Uniform Memory Access or Non-Uniform Memory Architecture is a computer memory design used in multiprocessors, where the memory access time depends on the memory location relative to a processor...
or
virtual memoryVirtual memory is a computer system technique which gives an application program the impression that it has contiguous working memory , while in fact it may be physically fragmented and may even overflow on to disk storage. Systems that use this technique make programming of large applications...
, 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.
Roundoff control
In computations with rounded arithmetic, e.g. with
floating pointIn computing, floating point describes a system for numerical representation in which a string of digits represents a rational number....
numbers, a divide-and-conquer algorithm may yield more accurate results than a superficially equivalent iterative method. For example, one can add
N numbers either by a simple loop that adds each datum to a single variable, or by a D&C algorithm that breaks the data set into two halves, recursively computes the sum of each half, and then adds the two sums. While the second method performs the same number of additions as the first, and pays the overhead of the recursive calls, it is usually more accurate.
Recursion
Divide-and-conquer algorithms are naturally implemented as
recursive proceduresIn computer science, a subroutine or subprogram is a portion of code within a larger program, which performs a specific task and is relatively independent of the remaining code....
. In that case, the partial sub-problems leading to the one currently being solved are automatically stored in the
procedure call stackIn computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, control stack, function stack, or run-time stack, and is often shortened to just "the stack"...
.
Explicit stack
Divide and conquer algorithms can also be implemented by a non-recursive program that stores the partial sub-problems in some explicit data structure, such as a
stackIn computer science, a stack is a last in, first out abstract data type and data structure. A stack can have any abstract data type as an element, but is characterized by only two fundamental operations: push and pop. The push operation adds to the top of the list, hiding any items already on the...
, queue, or
priority queueA priority queue is an abstract data type in computer programming that supports the following three operations:* InsertWithPriority: add an element to the queue with an associated priority...
. This approach allows more freedom in the choice of the sub-problem that is to be solved next, a feature that is important in some applications — e.g. in breadth-first recursion and the
branch and boundBranch and bound is a general algorithm for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization...
method for function optimization. This approach is also the standard solution in programming languages that do not provide support for recursive procedures.
Stack size
In recursive implementations of D&C algorithms, one must make sure that there is sufficient memory allocated for the recursion stack, otherwise the execution may fail because of
stack overflowIn software, a stack overflow occurs when too much memory is used on the call stack. In many programming languages, the call stack contains a limited amount of memory, usually determined at the start of the program. The size of the call stack depends on many factors, including the programming...
. Fortunately, D&C algorithms that are time-efficient often have relatively small recursion depth. For example, the quicksort algorithm can be implemented so that it never requires more than nested recursive calls to sort items.
Stack overflow may be difficult to avoid when using recursive procedures, since many compilers assume that the recursion stack is a contiguous area of memory, and some allocate a fixed amount of space for it. Compilers may also save more information in the recursion stack than is strictly necessary, such as return address, unchanging parameters, and the internal variables of the procedure. Thus, the risk of stack overflow can be reduced by minimizing the parameters and internal variables of the recursive procedure, and/or by using an explicit stack structure.
Choosing the base cases
In any recursive algorithm, there is considerable freedom in the choice of the
base cases, the small subproblems that are solved directly in order to terminate the recursion.
Choosing the smallest or simplest possible base cases is more elegant and usually leads to simpler programs, because there are fewer cases to consider and they are easier to solve. For example, an FFT algorithm could stop the recursion when the input is a single sample, and the quicksort list-sorting algorithm could stop when the input is the empty list; in both examples there is only one base case to consider, and it requires no processing.
On the other hand, efficiency often improves if the recursion is stopped at relatively large base cases, and these are solved non-recursively. This strategy avoids the overhead of recursive calls that do little or no work, and may also allow the use of specialized non-recursive algorithms that, for those base cases, are more efficient than explicit recursion. Since a D&C algorithm eventually reduces each problem or sub-problem instance to a large number of base instances, these often dominate the overall cost of the algorithm, especially when the splitting/joining overhead is low. Note that these considerations do not depend on whether recursion is implemented by the compiler or by an explicit stack.
Thus, for example, many library implementations of quicksort will switch to a simple loop-based
insertion sortInsertion sort is a simple sorting algorithm, a comparison sort in which the sorted array is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:* simple...
(or similar) algorithm once the number of items to be sorted is sufficiently small. Note that, if the empty list were the only base case, sorting a list with
n entries would entain
n+1 quicksort calls that would do nothing but return immediately. Increasing the base cases to lists of size 2 or less will eliminate most of those do-nothing calls, and more generally a base case larger than 2 is typically used to reduce the fraction of time spent in function-call overhead or stack manipulation.
Alternatively, one can employ large base cases that still use a divide-and-conquer algorithm, but implement the algorithm for predetermined set of fixed sizes where the algorithm can be completely
unrolledLoop unwinding, also known as loop unrolling, is a loop transformation technique that attempts to optimize a program's execution speed at the expense of its size....
into code that has no recursion, loops, or conditionals (related to the technique of
partial evaluationIn computing, partial evaluation is a technique for several different types of program optimization by specialization. The most straightforward application is to produce new programs which run faster than the originals but are guaranteed to behave in the same way...
). For example, this approach is used in some efficient FFT implementations, where the base cases are unrolled implementations of divide-and-conquer FFT algorithms for a set of fixed sizes. The large number of separate base cases desirable to implement this strategy efficiently are sometimes produced by source code generation methods.
Sharing repeated subproblems
For some problems, the branched recursion may end up evaluating the same sub-problem many times over. In such cases it may be worth identifying and saving the solutions to these overlapping subproblems, a technique commonly known as
memoizationIn computing, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously-processed inputs...
. Followed to the limit, it leads to bottom-up divide-and-conquer algorithms such as
dynamic programmingIn mathematics and computer science, dynamic programming is a method of solving complex problems by breaking them down into simpler steps. It is applicable to problems that exhibit the properties of overlapping subproblems and optimal substructure...
and chart parsing.
Algorithms that use Divide and conquer algorithm
- Merge Sort : It is a famous method to solve the sorting problem. In this method, to sort array of size n, first two half sub-arrays are sorted (each of size n/2), and then these sorted halves are merged in o(n) time to get the final sorted solution. Refer to Merge Sort
Merge sort is an O comparison-based sorting algorithm. In most implementations it is stable, meaning that it preserves the input order of equal elements in the sorted output. It is an example of the divide and conquer algorithmic paradigm...
for exact implementation details.
- Quick Sort : It is one of the most used methods for solving the sorting problem. Problem of sorting is divided into two sub-problems based on the partitioning the given array in two different ranges. Refer to Quick Sort for implementation details of partitioning and recursive process for quick sort using partitioning.
- Large number multiplication : Let and are n digit numbers, where each of , , , are n/2 digit numbers. Multiplication of these numbers:. Now here . So effectively we can calculate the multiplication of two digit numbers with only three digit numbers and some extra additions/subtractions (which are inherently simpler operations as compared to multiplication.). Similarly, two matrices can be multiplied using seven matrix multiplications, rather than eight, at the cost of some extra additions and subtractions. Refer Strassen algorithm
In the mathematical discipline of linear algebra, the Strassen algorithm, named after Volker Strassen, is an algorithm used for matrix multiplication...
for more details about this approach of matrix multiplication.
- Fast Fourier Transform : FFT is a famous algorithm for calculating Fourier transform. It can be used to multiply two degree n polynomials in time.
See also
- Mathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers. It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite...
- The Master theorem
In the analysis of algorithms, the master theorem, which is a specific case of the Akra-Bazzi theorem, provides a cookbook solution in asymptotic terms for recurrence relations of types that occur in practice...
- The Akra-Bazzi method
In computer science, the Akra–Bazzi method, or Akra–Bazzi theorem, is used to analyze the asymptotic behavior of the mathematical recurrences that appear in the analysis of divide and conquer algorithms where the sub-problems have substantially different sizes...
- Divide and rule
In politics and sociology, divide and rule is a combination of political, military and economic strategy of gaining and maintaining power by breaking up larger concentrations of power into chunks that individually have less power than the one implementing the strategy...
(politics and sociology)
- Binary search algorithm
In computer science, a binary search is an algorithm for locating the position of an element in a sorted list by checking the middle, eliminating half of the list from consideration, and then performing the search on the remaining half...
External links