wikipedia Divide-and-conquer algorithm

In computer science, divide and conquer is an 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.

NOTE:

1、"multi-branched recursion"如何理解

典型的，当"multi=2"的时候，就二分法了，这是经常采用的。

2、显然，"divide"几份，就对应了几个branch

This divide-and-conquer 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. the Karatsuba algorithm), finding the closest pair of points, syntactic analysis(e.g., top-down parsers), and computing the discrete Fourier transform (FFT).

Understanding and designing divide-and-conquer algorithms is a complex skill that requires a good understanding of the nature of the underlying problem to be solved. As when proving a theorem by induction, it is often necessary to replace the original problem with a more general or complicated problem in order to initialize the recursion, and there is no systematic method for finding the proper generalization.[clarification needed] These divide-and-conquer complications are seen when optimizing the calculation of a Fibonacci number with efficient double recursion.[why?][citation needed]

NOTE:

1、正如使用induction来证明一个定理，为了初始化递归，需要使用一个更加general或者更加complicate问题来替换原问题。

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.

NOTE:

1、recurrence relations 的意思是：递推关系

2、mathematical induction 的意思是: 数学归纳法

Decrease and conquer

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.

NOTE:

1、tail recursion: recursion to loop

Advantages

Solving difficult problems

Algorithm efficiency

Parallelism

NOTE:

1、需要思考，如何并行化divide and conquer algorithm

Memory access

NOTE:

1、这一段关于 memory、cache的论述是非常好的

Roundoff control

NOTE:

1、"Roundoff"的含义是 "圆整"