Divide and Conquer
摘要
The idea of divide-and-conquer is ubiquitous in our daily lives. When we pick up a new human language, we split our efforts into learning four basic subjects of a language, i.e., speaking, writing, reading, and listening. When a team of developers work on building a modern software program, they often divide the tasks: some members focus on back-end logic development, some on front-end User Interface (UI) design, some on the database, while others focus on product deployment using modern cloud technology. Divide-and-conquer is also a fundamental idea in computer science: it breaks down a complex problem into smaller problems (divide), attacks the subproblems separately (conquer), and combines the individual solutions to arrive at a final solution (combine). In this chapter, we will learn divide-and-conquer through a variety of examples, from guessing a number using binary search and merge sort/quick sort, through multiplication of two integers, to the Fast Fourier Transform. We will leverage the recursion technique we learned in Chapter 1 and apply it to implement divide-and-conquer solutions.