|
Early examples of these algorithms are primarily decrease and conquer – the original problem is successively broken down into ''single'' subproblems, and indeed can be solved iteratively.
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, "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>
Another notable example is the [[Karatsuba algorithm|algorithm]] invented by [[Anatolii Alexeevitch Karatsuba|Anatolii A. Karatsuba]] in 1960<ref>{{cite journal| last=Karatsuba | first=Anatolii A. | authorlink=Anatolii Alexeevitch Karatsuba |author2=Yuri P. Ofman |authorlink2=Yuri Petrovich Ofman | year=1962 | title=Умножение многозначных чисел на автоматах | journal=[[Doklady Akademii Nauk SSSR]] | volume=146 | pages=293–294}} Translated in {{cite journal| title=Multiplication of Multidigit Numbers on Automata | journal=Physics-Doklady | volume=7 | year=1963 | pages=595–596 |url={{Google books|MrkOAAAAIAAJ|plainurl=true}} }}</ref> that could multiply two ''n''-digit numbers in <math>O(n^{\log_2 3})</math> operations (in [[Big O notation]]). This algorithm disproved [[Andrey Kolmogorov]]'s 1956 conjecture that <math>\Omega(n^2)</math> operations would be required for that task.
As another example of a divide -and -conquer algorithm that did not originally involve computers, [[Donald Knuth]] gives the method a [[post office]] 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.<ref name=Knuth3>Donald E. Knuth, ''The Art of Computer Programming: Volume 3, Sorting and Searching'', second edition (Addison-Wesley, 1998).</ref> This is related to a [[radix sort]], described for [[IBM 80 series Card Sorters|punch-card sorting]] machines as early as 1929.<ref name=Knuth3/>
== Advantages ==
|
