Divide-and-conquer algorithm: Difference between revisions

Revision as of 08:14, 23 June 2019

Revision as of 22:49, 13 July 2019

Line 12:

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 (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="CormenLeiserson2009">{{cite book|author1=Thomas H. Cormen|author2=Charles E. Leiserson|author3=Ronald L. Rivest|coauthorsauthor4=Clifford Stein|title=Introduction to Algorithms|url=https://books.google.com/books?id=aefUBQAAQBAJ&printsec=frontcover#v=onepage&q=%22Divide-and-conquer%22&f=false|date=31 July 2009|publisher=MIT Press|isbn=978-0-262-53305-8}}</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)|loops]]. 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]].