Divide And Conquer Algorithm
In computer science, divide and conquer (D&C) is an important 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 technique is the basis of efficient algorithms for all kinds of problems, such as sorting (e.g., quicksort, merge sort), multiplying large numbers (e.g. Karatsuba), syntactic analysis (e.g., top-down parsers), and computing the discrete Fourier transform (FFTs).
On the other hand, the ability to understand and design D&C algorithms is a skill that takes time to master. As when proving a theorem by induction, it is often necessary to replace the original problem by a more general or complicated problem in order to get the recursion going, and there is no systematic method for finding the proper generalization.
The name "divide and conquer" is sometimes applied also to algorithms that reduce each problem to only one subproblem, such as the binary search algorithm for finding a record in a sorted list (or its analog in numerical computing, the bisection algorithm for root finding). 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 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. The name decrease and conquer has been proposed instead for the single-subproblem class.
The correctness of a divide and conquer algorithm is usually proved by mathematical induction, and its computational cost is often determined by solving recurrence relations.
Read more about Divide And Conquer Algorithm: Early Historical Examples
Famous quotes containing the words divide and, divide and/or conquer:
“Everything necessarily is or is not, and will be or will not be; but one cannot divide and say that one or the other is necessary. I mean, for example: it is necessary for there to be or not to be a sea-battle tomorrow; but it is not necessary for a sea-battle to take place tomorrow, or for one not to take place—though it is necessary for one to take place or not to take place.”
—Aristotle (384–322 B.C.)
“The king said, -Divide the living boy in two; then give half to the one, and half to the other. But the woman whose son was alive said to the king -because compassion for her son burned within her - -Please, my lord, give her the living boy; certainly do not kill him! The other said, -It shall be neither mine nor yours; divide it. Then the king responded: -Give the first woman the living boy; do not kill him. She is his mother.”
—Bible: Hebrew, 1 Kings. 3:25-37.
Solomon resolves a dispute between two women over a child. Solomon’s wisdom was proven by this story.
“Only a fully trained Jedi knight with the Force as his ally will conquer Vader and his emperor. If you end your training now—if you choose the quick and easy path, as Vader did—you will become an agent of evil.”
—Leigh Brackett (1915–1978)