Divide and conquer, originally a political maxim, designates an algorithm design paradigm in which a problem is recursively broken down into two or more sub-problems of the same or related type until they become simple enough to be solved directly, and the solutions to the sub-problems are then combined to give a solution to the original problem. It is the basis of efficient algorithms for many problems, such as sorting with quicksort and merge sort, multiplying large numbers with the Karatsuba algorithm, finding the closest pair of points, top-down parsing, SAT solving and computing the discrete Fourier transform. Algorithms recorded in this atlas are grouped here when their design technique is divide and conquer.
Facts
Core PrincipleSolve small instances directly, otherwise divide the problem into two or more smaller instances, solve each recursively and combine the solutions. 1 Connections
In Field
Technique Used By
Source Collective operation (Wikipedia)
Source IBM: What is a decision tree?
Source Wikipedia: Symbolic regression
Sources
1. NIST DADS: divide and conquer
DefinitionQuote, Definition
Solve a problem, either directly because solving that instance is easy (typically, because the instance is small) or by dividing it into two or more smaller instances. Each of these smaller instances is recursively solved, and the solutions are combined to produce a solution for the original instance.
Wikipedia: Divide-and-conquer algorithm
Wikipedia, lead sectionQuote, Wikipedia, lead section
A divide-and-conquer algorithm 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.
Wikipedia: Symbolic regression
Technique Used By: Symbolic Regression, Article bodyQuote, Technique Used By: Symbolic Regression, Article body
This is an example of divide and conquer, which reduces the size of the problem to be more manageable.
Collective operation (Wikipedia)
Technique Used By: Collective operation, Article bodyQuote, Technique Used By: Collective operation, Article body
Since an implementation by means of a sequential for-loop with p − 1 {\displaystyle p-1} iterations becomes a bottleneck, divide-and-conquer approaches are common.
IBM: What is a decision tree?
IBMTechnique Used By: Decision tree learning, Section on how decision tree learning worksQuote, Technique Used By: Decision tree learning, Section on how decision tree learning works
Decision tree learning employs a divide and conquer strategy by conducting a greedy search to identify the optimal split points within a tree.
Wikipedia: Divide-and-conquer algorithm
WikipediaIn Group: Algorithm Design Strategies, LeadQuote, In Group: Algorithm Design Strategies, Lead
In computer science, divide and conquer, originally a political maxim, designates an algorithm design paradigm.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.