Divide-and-conquer algorithm: Difference between revisions

Revision as of 23:02, 24 May 2019

Revision as of 18:15, 28 May 2019

Line 3:

This divide-and-conquer technique is the basis of efficient algorithms for all kinds of 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]]).{{Citation needed|date=October 2017}}

Understanding and designing divide-and-conquer algorithms is a complex skill that requires a good understanding of the nature of the underlying problem to be solved. As when proving a [[theorem]] by [[Mathematical induction|induction]], it is often necessary to replace the original problem with a more general or complicated problem in order to initialize the recursion, and there is no systematic method for finding the proper generalization.{{Clarify|date=October 2017}} These divide-and-conquer complications are seen when optimizing the calculation of a [[Fibonacci_numberFibonacci number#Matrix form|Fibonacci number with efficient double recursion]].{{Why|date=October 2017}}{{Citation needed|date=October 2017}}

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

Line 55:

=== Recursion ===

Divide-and-conquer algorithms are naturally implemented as [[Recursion_Recursion (computer_sciencecomputer science)|recursive procedures]]. In that case, the partial sub-problems leading to the one currently being solved are automatically stored in the [[call stack|procedure call stack]]. A recursive function is a function that calls itself within its definition.

=== Explicit stack ===

Line 94:

== References ==

<references/>

{{DEFAULTSORT:Divide And Conquer Algorithm}}