Contents

1. 1. 基本概念
2. 2. 基本思想及策略
3. 3. 分治法适用的情况
4. 4. 基本步骤
5. 5. 复杂性分析
6. 6. 示例： 归并排序
7. 7. 可使用分治法求解的一些经典问题
8. 8. 分治法设计程序时的思维过程

基本概念

　　在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”（Divide and Conquer），就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……
　　任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。

基本思想及策略

　　分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
　　分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
　　如果原问题可分割成k个子问题，1< k≤n，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

分治法适用的情况

　　分治法所能解决的问题一般具有以下几个特征：

• 该问题的规模缩小到一定的程度就可以容易地解决。绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加

• 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。这条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用。

• 利用该问题分解出的子问题的解可以合并为该问题的解。这条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。
• 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。这条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

基本步骤

　　分治法在每一层递归上都有三个步骤：
　　step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
　　step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
　　step3 合并：将各个子问题的解合并为原问题的解。

　　它的一般的算法设计模式如下：

Divide-and-Conquer(P)
    1. if |P|≤n0
    2. then return(ADHOC(P))
    3. 将P分解为较小的子问题 P1 ,P2 ,...,Pk
    4. for i←1 to k
    5. do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi
    6. T ← MERGE(y1,y2,...,yk) △ 合并子问题
    7. return(T)

　　其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC(P)求解。算法MERGE(y1,y2,…,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,…,Pk的相应的解y1,y2,…,yk合并为P的解。

复杂性分析

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

　　通过迭代法求得方程的解：
　　递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当 mi≤n< mi+1　时，T(mi)≤T(n)< T(mi+1)。

示例： 归并排序

　　归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。以二路归并为例：

　　代码示例：

#include <iostream>
using namespace std;

//将有二个有序数列a[first...mid]和a[mid...last]合并。
void mergearray(int a[], int first, int mid, int last, int temp[]){
    int i = first, j = mid + 1;
    int m = mid,   n = last;
    int k = 0;
    
    while (i <= m && j <= n){
        if (a[i] <= a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }
    while (i <= m)
        temp[k++] = a[i++];
    while (j <= n)
        temp[k++] = a[j++];

    for (i = 0; i < k; i++)
        a[first + i] = temp[i];
}

void mergesort(int a[], int first, int last, int temp[]){
    if (first < last){
        int mid = (first + last) / 2;
        mergesort(a, first, mid, temp);    //左边有序
        mergesort(a, mid + 1, last, temp); //右边有序
        mergearray(a, first, mid, last, temp); //再将二个有序数列合并
     }
}

bool MergeSort(int a[], int n){
    int *p = new int[n];
    if (p == NULL)
        return false;
    mergesort(a, 0, n - 1, p);
    delete[] p;
    return true;
}

int main(){
    int arr[] = {1, 5, 2, 4, 6, 3, 2, 6};
    
    MergeSort(arr, 8);
    
    for (int i = 0; i < 8; ++i){
        cout<<arr[i]<<" ";
    }
    
    cout<<endl;
}

可使用分治法求解的一些经典问题

• 二分搜索
• 大整数乘法
• Strassen矩阵乘法
• 棋盘覆盖
• 归排序
• 快速排序
• 线性时间选择
• 最接近点对问题
• 循环赛日程表
• 汉诺塔

分治法设计程序时的思维过程

　　实际上就是类似于数学归纳法，找到解决本问题的求解方程公式，然后根据方程公式设计递归程序。
　　1、一定是先找到最小问题规模时的求解方法；
　　2、然后考虑随着问题规模增大时的求解方法；
　　3、找到求解的递归函数式后（各种规模或因子），设计递归程序即可。 　　

auther: 红脸书生