算法设计与分析 2.2 分治法基本思想

分治法基本思想是将一个规模为 n 的问题分解成为 k 个规模较小的子问题，这些子问题相互独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

DivideAndConquer(P) {
    if (|P| < f) 
        adhoc(P);
    else {
        divide P into smaller subinstances P1, P2, P3, ..., Pk;
        for (int i = 1; i <= k; i++)
            yi = DivideAndConquer(Pi);
        return merge(y1, y2, y3, ..., yk);
    }
}

 

其中|P|表示问题P的规模。f 为一阀值，表示当问题的规模不超过 f 时，问题已经容易解出，不必再继续分解。