递归与分治策略(三)

分治法的基本思想

分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同。递归地解这些问题,然后将各子问题的解合并得到原问题的解,它的一般算法设计模式如下:

divide-and-conquer(P)
{
    if(|P|<=n0) adhoc(P);  
    for(i=1;i<=k;i++)//divida P into smaller subinstances P1,P2,...,PK;
        yi=divide-and-conquer(Pi);
    return merge(y1,y2,...,yk);
}

继续阅读“递归与分治策略(三)”