首页 > 代码库 > 分治算法

分治算法

【分治法的设计思想】
将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。
最后把每个小问题的解答组合起来,可得到原问题的答案。

【分治法的适用条件】

该问题的规模缩小到一定的程度就可以容易地解决;
该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质
利用该问题分解出的子问题的解可以合并为该问题的解;
该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。

【分治法的基本步骤】

divide-and-conquer(P)
 {
    if ( | P | <= n0) adhoc(P);   //解决小规模的问题
    divide P into smaller subinstances P1,P2,...,Pk;//分解问题
    for (i=1,i<=k,i++)
        yi=divide-and-conquer(Pi);  //递归的解各子问题
    return merge(y1,...,yk);  //将各子问题的解合并为原问题的解
 }   
 

【分治法的复杂性分析】

一个分治法将规模为n的问题分成k个规模为n/m的子问题去解。
设分解阀值n0=1,且adhoc解规模为1的问题耗费1个单位时间。
再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。
用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间,则有:

技术分享

通过迭代法求得方程的解:

技术分享

 

分治算法