Divide-and-conquer algorithm: Difference between revisions

Revision as of 09:03, 11 February 2025

Latest revision as of 18:25, 17 August 2025

(3 intermediate revisions by 3 users not shown)

Line 4:

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 [[Recursion (computer science)|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.

== Divide and conquer ==

[[File:Merge sort algorithm diagram.svg|thumb|Divide-and-conquer approach to sort the list (38, 27, 43, 3, 9, 82, 10) in increasing order. ''Upper half:'' splitting into sublists; ''mid:'' a one-element list is trivially sorted; ''lower half:'' composing sorted sublists.]]

The divide-and-conquer [[Programming paradigm|paradigm]] is often used to find an optimal solution of a problem. Its basic idea is to decompose a given problem into two or more similar, but simpler, subproblems, to solve them in turn, and to compose their solutions to solve the given problem. Problems of sufficient simplicity are solved directly.

For example, to sort a given list of ''n'' [[Natural number|natural numbers]], split it into two lists of about ''n''/2 numbers each, sort each of them in turn, and interleave both results appropriately to obtain the sorted version of the given list (see the picture). This approach is known as the [[merge sort]] algorithm.

Line 41:

* if the number of subproblems <math>q > 2</math>, then the divide-and-conquer algorithm's running time is bounded by <math>O(n^{\log_{2}q})</math>.

* if the number of subproblems is exactly one, then the divide-and-conquer algorithm's running time is bounded by <math>O(n)</math>.<ref name="kleinberg&Tardos">{{cite book |last1=Kleinberg |first1=Jon |last2=Tardos |first2=Eva |title=Algorithm Design |date=March 16, 2005 |publisher=[[Pearson Education]] |isbn=9780321295354 |pages=214-220214–220 |edition=1 |url=https://www.pearson.com/en-us/subject-catalog/p/algorithm-design/P200000003259/9780137546350 |access-date=26 January 2025}}</ref>

If, instead, the work of splitting the problem and combining the paritalpartial solutions take <math>cn^2</math> time, and there are 2 subproblems where each has size <math>\frac{n}{2}</math>, then the running time of the divide-and-conquer algorithm is bounded by <math>O(n^2)</math>.<ref name="kleinberg&Tardos"/>

=== Parallelism ===

Line 90:

* {{annotated link|Akra–Bazzi method}}

* {{annotated link|Decomposable aggregation function}}

* {{annotated link|Divide and ruleconquer|"Divide and conquer"}}

* {{annotated link|Fork–join model}}

* {{annotated link|Master theorem (analysis of algorithms)}}