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. 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. Another divide and conquer algorithm with a single subproblem 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 Gauss's 1805 description of what is now called the Cooley-Tukey fast Fourier transform (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 sort algorithm, invented by John von Neumann in 1945.
Another notable example is the algorithm invented by Anatolii A. Karatsuba in 1960 that could multiply two n-digit numbers in operations (in Big O notation). This algorithm disproved Andrey Kolmogorov'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, 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. This is related to a radix sort, described for punch-card sorting machines as early as 1929.
Read more about this topic: Divide And Conquer Algorithm
Famous quotes containing the words early, historical and/or examples:
“Many a woman shudders ... at the terrible eclipse of those intellectual powers which in early life seemed prophetic of usefulness and happiness, hence the army of martyrs among our married and unmarried women who, not having cultivated a taste for science, art or literature, form a corps of nervous patients who make fortunes for agreeable physicians ...”
—Sarah M. Grimke (1792–1873)
“Some of us still get all weepy when we think about the Gaia Hypothesis, the idea that earth is a big furry goddess-creature who resembles everybody’s mom in that she knows what’s best for us. But if you look at the historical record—Krakatoa, Mt. Vesuvius, Hurricane Charley, poison ivy, and so forth down the ages—you have to ask yourself: Whose side is she on, anyway?”
—Barbara Ehrenreich (b. 1941)
“In the examples that I here bring in of what I have [read], heard, done or said, I have refrained from daring to alter even the smallest and most indifferent circumstances. My conscience falsifies not an iota; for my knowledge I cannot answer.”
—Michel de Montaigne (1533–1592)