Divide, Combine, and Conquer
Divide and rule, a sound motto;Unite and lead, a better one.
— Johann Wolfgang von Goethe, Gedichte
This chapter is the first of three dealing with well-known design strategies. The strategy dealt with in this chapter, divide and conquer (or simply D&C), is based on decomposing your problem in a way that improves performance. You divide the problem instance, solve subproblems recursively, combine the results, and thereby conquer the problem—a pattern that is reflected in the chapter title.1
Tree-Shaped Problems: All About the Balance
I have mentioned the idea of a subproblem graph before: We view subproblems ...