Content deleted Content added
m Reverted 1 edit by 213.55.95.205 (talk) to last revision by AdaHephais |
+link |
||
Line 2:
In [[computer science]], '''divide and conquer''' is an [[algorithm design paradigm]]. A divide-and-conquer [[algorithm]] [[Recursion (computer science)|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 |author1-link=Richard Blahut |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.
| |||