Divide-and-conquer algorithm: Difference between revisions

Revision as of 14:02, 6 March 2019

Revision as of 23:02, 24 May 2019

Line 25:

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=Soviet 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/>