Divide-and-conquer algorithm: Difference between revisions

Revision as of 23:44, 9 December 2018

Revision as of 23:48, 9 December 2018

Line 8:

== 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 paradigm is often used to find the 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 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 (cf.see the picture). This approach is known as the [[merge sort]] algorithm.

The name "divide and conquer" is sometimes applied to algorithms that reduce each problem to only one sub-problem, such as the [[binary search]] algorithm for finding a record in a sorted list (or its analog in [[numerical algorithm|numerical computing]], the [[bisection algorithm]] for [[root-finding algorithm|root finding]]).<ref name=CLR>Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, ''Introduction to Algorithms'' (MIT Press, 2000).</ref> These algorithms can be implemented more efficiently than general divide-and-conquer algorithms; in particular, if they use [[tail recursion]], they can be converted into simple [[loop (computing)|looploops]]s. Under this broad definition, however, every algorithm that uses recursion or loops could be regarded as a "divide -and -conquer algorithm". Therefore, some authors consider that the name "divide and conquer" should be used only when each problem may generate two or more subproblems.<ref>Brassard, G. and Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.</ref> The name '''decrease and conquer''' has been proposed instead for the single-subproblem class.<ref>Anany V. Levitin, ''Introduction to the Design and Analysis of Algorithms'' (Addison Wesley, 2002).</ref>

An important application of divide and conquer is in optimization,{{Examples|date=October 2017}}, where if the search space is reduced ("pruned") by a constant factor at each step, the overall algorithm has the same asymptotic complexity as the pruning step, with the constant depending on the pruning factor (by summing the [[geometric series]]); this is known as [[prune and search]].

== Early historical examples ==