Title:算法设计与分析学习笔记（一）：分治法
Date: 2014-12-08 15:55
Category: 算法学习
分治法
Slug: algorithm_devide_method
Author: Boqing Ann
Summary: 分治法的基本思想 ,适用条件，基本步骤

分治法

---

1.分治法的基本思想

---

分治法的设计思想是将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治法将一个大规模问题分解为若干子问题（子问题是原问题的小模式），将子问题的解合并后就可以得到原问题的解，具体可以使用递归计数来完成。分治有两个特点：

1.子问题相互独立且与原问题形式相同
2.反复分治，使划分得到的子问题小到不能再分时，直接对其求解

2.分治法的适用条件

---

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

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

上述第一条特征是绝大多数问题都能满足的，因为计算复杂性一般随着规模的减小而降低。
第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用。
第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征。
如果具备了第一条特征和第二条特征，而子问题的解不可以合并，则可以考虑贪心算法或动态规划
第四条特征涉及分治法的效率，如果各子问题不是独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

---

3.分治法的基本步骤

---

分治法在每一层递归上都有如下三个步骤：

1.分解。 将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。
2.求解。 若子问题规模较小而容易求解则直接求解，否则递归的解决各个子问题。
3.合并。 将各个子问题的解合并为原问题的解。

人们从大量的实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。换句话说，将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取k=2。这种使得子问题规模大致相等的做法是出自一种平衡子问题的思想，它几乎总是比子问题规模不等的做法要好。

分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显，有些问题的合并方法比较复杂，究竟应该怎样合并，没有统一的模式。

分治法的一般算法框架如下:

divide_and_conquer(problem)
{
    if(|problem| < n) adhoc(problem);            /*解决小规模的问题*/
    divide Problem into smaller subinstances P1,P2,....Pk;/*分解问题*/
    for(i = 1; i<= k(子问题个数); ++i){
        result[i] = divide_and_conquer(P[i]);   /*递归的解各个子问题*/
    }
    return merge(result[1]...result[k]);    /*将各个子问题的解合并为原问题的解*/
}

采用分治法思想设计的算法进行分析时，可用如下递归方程描述算法的运行时间T(n)

$$T(n) = \begin{cases} θ(1), & \text{if $n$ less than 最小可求解规模} \\ kT(\frac{n}{m}) + D(n) + C(n), & \text{if $n$ is great than 最小可求解规模} \end{cases}$$

在该递归方程中，如果问题的规模足够小，可以直接求解，则T(n) = O(1)。如果问题规模不够小，还需分解为k个规模大小为$\frac{n}{m}$的子问题，而且分析问题与合并问题的时间分别为 D(n) , C(n) ,则$T(n) = kT(\frac{n}{m}) + D(n) + C(n)$ 。
对于该方程，不妨设 n 为 m 的幂 ，记D(n) = $C_1$(n)+$C_2$(n) , 则该递归方程的解为

$$T(n) = n^{{log_m}^n} + \sum^{{log_m}^{n-1}}_{i = 0}k^i D(n/m^i)$$

---

4. 分治法的典型实例

4.1 折半查找(二分搜索）

问题描述：给定已按照升序排列好的n个元素 a[0:n-1]，现在要在这n个元素中找出一特定元素。

问题分析：采用分治法的思想，充分利用元素之间已经存在的次序关系，将序列划分为两个个数相同的左右两个部分，取最中间的元素和x进行比较，如果等于中间的元素就找到，如果不等于，就递归的在左边（x<中间值）或者右边(x>中间值）二分查找。

注意事项:对于二分查找，一般需要建立两个不变性：

1.当前待查找序列，肯定包含目标元素
2.每次待查找序列的规模都会变小。

1用来防止，把目标元素错过,2可以保证程序最终会终止。每次循环的分支内，保证这样的两个不变性可以满足，那么这样的二分查找程序一般不会含有逻辑错误。

template<class T>
int binary_search(T arr[],T key){
    int low = 0;
    int high = arr.size()-1;
    while(low<=high){
        int mid = low + (high-low)/2; // 注意mid =begin+(end-begin)/2,用mid=(begin+end)/2是有溢出危险的
        if(arr[mid]<key){
            low = mid+1;
        }else if(arr[mid]>key){
            high = mid-1;
        }else{
            return arr[mid];
        }
    }
    return -1;
}

Knuth在其The Art of Computer Programming Volume 3:Sorting and Searching的6.2.1节的历史部分中指出，虽然第一篇二分搜索论文在1946年就发表了，但是地一个没有错误的二分搜索程序却直到1962年才出现。

几个错误的例子