Content deleted Content added
No edit summary |
Citation bot (talk | contribs) Add: bibcode, date, authors 1-2. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_toolbar |
||
Line 2:
In [[computer science]], '''divide and conquer''' is an [[algorithm design paradigm]]. A divide-and-conquer [[algorithm]] recursively breaks 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.
The divide-and-conquer technique is the basis of efficient algorithms for many problems, such as [[sorting algorithm|sorting]] (e.g., [[quicksort]], [[merge sort]]), [[multiplication algorithm|multiplying large numbers]] (e.g., the [[Karatsuba algorithm]]), finding the [[Closest pair of points problem|closest pair of points]], [[syntactic analysis]] (e.g., [[top-down parser]]s), and computing the [[discrete Fourier transform]] ([[fast Fourier transform|FFT]]).<ref>{{cite book |last1=Blahut |first1=Richard |title=Fast Algorithms for Signal Processing |date=14 May 2014 |publisher=Cambridge University Press |isbn=978-0-511-77637-3 |pages=139–143}}</ref>
Designing efficient divide-and-conquer algorithms can be difficult. As in [[mathematical induction]], it is often necessary to generalize the problem to make it amenable to a recursive solution. The correctness of a divide-and-conquer algorithm is usually proved by mathematical induction, and its computational cost is often determined by solving [[recurrence relation]]s.
Line 24:
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 | author-link=Donald Knuth | year=1998 | title=The Art of Computer Programming: Volume 3 Sorting and Searching | url=https://archive.org/details/artofcomputerpro03knut | url-access=limited | page=[https://archive.org/details/artofcomputerpro03knut/page/159 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. | author-link=Anatolii Alexeevitch Karatsuba |author2=Yuri P. Ofman |author-link2=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 | bibcode=1963SPhD....7..595K |url={{Google books|MrkOAAAAIAAJ|plainurl=true}} | last1=Karatsuba | first1=A. | last2=Ofman | first2=Yu. }}</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/>
| |||