Content deleted Content added
m WP:AWB cleanup, replaced: → |
adding links to references using Google Scholar |
||
Line 12:
For example, to sort a given list of ''n'' natural numbers, split it into two lists of about ''n''/2 numbers each, sort each of them in turn, and interleave both results appropriately to obtain the sorted version of the given list (see the picture). This approach is known as the [[merge sort]] algorithm.
The name "divide and conquer" is sometimes applied to algorithms that reduce each problem to only one sub-problem, such as the [[binary search]] algorithm for finding a record in a sorted list (or its analog in [[numerical algorithm|numerical computing]], the [[bisection algorithm]] for [[root-finding algorithm|root finding]]).<ref name=
An important application of divide and conquer is in optimization,{{Examples|date=October 2017}} where if the search space is reduced ("pruned") by a constant factor at each step, the overall algorithm has the same asymptotic complexity as the pruning step, with the constant depending on the pruning factor (by summing the [[geometric series]]); this is known as [[prune and search]].
Line 21:
Binary search, a decrease-and-conquer algorithm where the subproblems are of roughly half the original size, has a long history. While a clear description of the algorithm on computers appeared in 1946 in an article by [[John Mauchly]], the idea of using a sorted list of items to facilitate searching dates back at least as far as [[Babylonia]] in 200 BC.<ref name=Knuth3/> Another ancient decrease-and-conquer algorithm is the [[Euclidean algorithm]] to compute the [[greatest common divisor]] 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 [[Carl Friedrich Gauss|Gauss]]'s 1805 description of what is now called the [[Cooley–Tukey FFT algorithm|Cooley–Tukey fast Fourier transform]] (FFT) algorithm,<ref name=Heideman84>Heideman, M. T., D. H. Johnson, and C. S. Burrus, "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.331.4791&rep=rep1&type=pdf Gauss and the history of the fast Fourier transform]", IEEE ASSP Magazine, 1, (4), 14–21 (1984).</ref> although he did not [[analysis of algorithms|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 sort]] algorithm, invented by [[John von Neumann]] in 1945.<ref>{{ cite book | last=Knuth | first=Donald | authorlink=Donald Knuth | year=1998 | title=[[The Art of Computer Programming]]: Volume 3 Sorting and Searching | page=159 | isbn=0-201-89685-0 }}</ref>
Line 44:
=== Memory access ===
Divide-and-conquer algorithms naturally tend to make efficient use of [[memory cache]]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 algorithm|cache-oblivious]]'', because it does not contain the cache size as an explicit parameter.<ref name="cahob">{{cite journal | author = M. Frigo |author2=C. E. Leiserson |author3=H. Prokop | title = Cache-oblivious algorithms | journal = Proc. 40th Symp. on the Foundations of Computer Science | year = 1999|url=https://dspace.mit.edu/bitstream/handle/1721.1/80568/43558192-MIT.pdf;sequence=2}}</ref>
Moreover, D&C algorithms can be designed for important algorithms (e.g., sorting, FFTs, and matrix multiplication) to be ''optimal'' cache-oblivious algorithms–they use the cache in a probably optimal way, in an asymptotic sense, regardless of the cache size. In contrast, the traditional approach to exploiting the cache is ''blocking'', as in [[loop nest optimization]], 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.
Line 50:
=== Roundoff control ===
In computations with rounded arithmetic, e.g. with [[floating-point]] 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 called [[pairwise summation]] 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.<ref>Nicholas J. Higham, "[https://pdfs.semanticscholar.org/5c17/9d447a27c40a54b2bf8b1b2d6819e63c1a69.pdf The accuracy of floating point summation]", ''SIAM J. Scientific Computing'' '''14''' (4), 783–799 (1993).</ref>
== Implementation issues ==
| |||