算法学习：分治法（第4节）

分治法的基本思想

将规模为N的问题划分为k个规模较小且彼此独立的子问题,每个子问题各自独立地求解后再将所有子问题的解综合得到原问题的解答.如果这些子问题是相对较大的,则继续采用分治策略对它们进行分解处理,直至所有待解决的问题都简化为可以直接解决的基本情形.

什么情况适合分治法？

1. 当一个问题被缩小到一定规模时，则较为简便地得以解决；
2. 一个大优化问题是可划分为若干较小规模且性质相同的优化子problem，并且这些subproblems都具有optimal substructure特性；
3. 将这些subproblems各自求解后所得的结果可以通过某种方式结合起来或整合起来，则能够构建出较大scale下的problem solution；
4. 各subproblems在划分时彼此之间互不干扰地进行划分，并且它们之间没有共同的目标subproblem。

分治法的求解过程： 划分——》求子问题——》合并

 divide_and_conquer(P)

    
 {
    
 	if ( |P| <= n0 )   //解决小规模的问题