Content deleted Content added
In my opinion, it is fairly widely known that the listed algorithms are D&C algorithms. I don't think a citation is needed. |
Undid revision 886376735 by 2607:FEA8:1D20:981:9577:349F:7FF8:6A22: to non-computer-scientists, not even the algorithms themselves are usually known |
||
Line 1:
In [[computer science]], '''divide and conquer''' is an [[algorithm design paradigm]] based on multi-branched [[recursion]]. A divide-and-conquer [[algorithm]] works by recursively breaking 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.
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_number#Matrix form|Fibonacci number with efficient double recursion]].{{Why|date=October 2017}}{{Citation needed|date=October 2017}}
| |||