Divide and Conquer

Definition: An algorithmic technique. To solve a problem on an instance of size n, a solution is found either directly because solving that instance is easy (typically, because the instance is small) or the instance is separated into two or more smaller instances. Each of these smaller instances is solved and the solutions are combined to produce a solution for the original instance.

The name divide and conquer is because the problem is conquered by dividing it into several smaller problems.

This technique yields elegant, simple and quite often very efficient algorithms. Well-known examples include heapify, merge sort, quicksort, Strassen's fast matrix multiplication, the Fast Fourier Transform (FFT), and binary search. (Why is binary search included? The dividing part just picks which segment in which to search, and "combining the solutions" is trivial: take the answer from the segment in which you searched.) Similar principles are at the heart of several important data structures such as binary search tree, multiway search trees, tries, skip lists, multidimensional search trees (k-d trees, quadtrees), etc.

Copyright © 2024 by Phillip Paul Fuchs, all rights reserved.
Abstracting with credit is permitted...