在上一篇文章中，我们已经学习了算法时间复杂度的基本知识。现在我们开始进入真正的算法的介绍——分治策略(divide-and-conquer strategy)。

分治与递归的基本概念

分治策略是一种普遍的算法思想，拆开来看，“分”是分开，“治”是治理，“分治”就是“分而治之"，把一个问题分成几个小问题求解。分治策略主要包含三个步骤：

①分解：将问题划分成若干个子问题，这些子问题与原问题形式一样，只是规模更小

②解决：求解子问题

③合并：由子问题的解得到原问题的解

既然子问题和原问题是同一种形式的，那么如果对于原问题可以用分治策略进行求解，那么子问题应该就也可以应用同样的策略。
这样，求解原问题需要求解子问题，求解子问题又需要求解子子问题，求解子子问题又需要求解子子子问题。这种调用自身不停地向下求解的过程就叫做递归(recursion)。
递归其实有很多例子。不知道大家有没有见过投屏时大屏套小屏的场景:
这就是一种递归。录屏软件想要捕获显示器的内容并由窗口显示出来，但是显示器内容又包括自身的窗口，这就造成了录屏软件想要捕获显示器，就必须捕获自身窗口和除了自身窗口以外的内容，而自身窗口又需要捕获显示器，也就是我们说的“无限套娃”。理论上，这种递归是无限的，而事实上，系统为了防止它无限调用把系统资源占尽搞崩，所以设置了一个尽头。
按照这个原理，我们用C语言也可以写出一个无限递归的函数：

void func(){
    printf("function called\n");
    func();
}

结果为

而我们不想要无限递归，因为这无法解决我们的问题。我们想要递归有一个尽头，这个尽头叫做递归的边界条件。
例如上面那个函数func()，想要让它能够自己停下来，可以变成：

void func(int n){
    if(n <= 0)
        return;
    printf("function called\n");
    func(n - 1);
}

n≤0就是递归的边界条件。调用时，只需要func(5)，每执行一次递归，传入函数的实参相比于上一层都会-1，相当于脱一件衣服，直到减到0，这个时候返回，也就是递归从底向上一层层地穿上衣服，直到最顶层。
递归过程在系统中具体的实现方式，感兴趣的可以学习一下汇编语言，或者直接上网搜一下。作为算法导论系列，再展开篇幅就太长了。
同样地，函数表达式也会出现递归的情况。例如斐波那契数列
0,1,1,2,3,5,8,13,21…每项为前两项之和，数列的定义为

$F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)$
其中F(0)=0, F(1)=1就是边界条件。
带着这些知识，我们来学习分治算法的第一个例子——二分查找

二分查找

玩过猜数游戏吗？甲心中想一个从1到100的数，乙说一个数，甲回答这个数比心里想的数大还是小，直到乙找到这个数为止。
你会怎么猜？先猜50，小了，再猜75，大了，再猜62，对不对？
这就是二分查找。二分查找(binary search)也称折半查找，是一种基于顺序表（与链表相对）的查找方法，它要求数据必须要先排好顺序。二分查找的思想是：假设表按照升序排序，将该表的中间元素（即中位数）与待查找的数比较，如果中位数小于待查数（说明中位数太小了，待查数一定在比它大的数中），则查找表的后一半；如果中位数大于待查数，则查找表的前一半，若中位数等于待查数，那中位数就是要找的数。查找表的前一半时或后一半时，也同样执行以上紫红色字的步骤。过程要调用自身，这就是递归过程。这样相当于每次缩小一半的搜索范围，将搜索不断细化，找到什么时候为止呢？找到剩下的范围一下就可以找出那个数为止。

例如有这样一列数：

第一行从0到14是数组（顺序表）的下标。假设我们想在这个表中寻找63是否存在，如果存在是第几个。为了标记查找的范围，设置一个low变量指向表的起始，high变量指向表的结尾，我们要找到中位数，所以mid变量指向表的中间位置，也就是$mid=\lfloor (low+high)/2\rfloor$

mid指向的数是36，比63要小，这个时候就要在表的右半部分进行查找，在对右半部分查找的时候，low的位置就应该变成右半部分的起始，也就是low = mid + 1，相应地，mid位置也要发生变化：
mid指向的数是72，又比63大了，这个时候要在左半部分查找，但是注意我们的表已经缩小到整个表的右半部分了，所以再取左半部分，high = mid - 1，也就是这个位置：

mid指向50，比63小，再在右半部分查找，low = mid + 1：

正好找到了，那就返回mid的值——10。至此，就完成了查找的任务。
那么如果63不在这个表中，比如我把表中的63改成62呢？那么这时mid比63小，low=mid+1：
可以看到low已经比high大了，表的长度变成0了，这就是说，表的查找范围已经缩小成1了，在这一个数里还找不到想要的那个数，那再缩小就没了。至此，查找结束，没有找到63这个数。
在代码中，我们用递归的方式实现二分查找的过程。

（第一次用LaTeX写伪代码，不是那么好看）
C语言代码：

#include<stdio.h>
int binarySearch(int* arr, int x, int low, int high){
    if(low > high)
        return -1;
    int mid = (low + high) / 2;//这里有人说为了防止low+high溢出，应该使用low+(high-low)/2，但是为了清晰，这里就不这么写了。
    if(arr[mid] == x)
        return mid;
    if(arr[mid] < x)
        return binarySearch(arr, x, mid + 1, high);
    return binarySearch(arr, x, low, mid - 1);//省略了if(arr[mid] > x)，因为只剩这一种情况了
}
int main(){
    int arr[10] = {1,2,3,4,5,6,7,8,9,10};
    printf("element position: %d", binarySearch(arr,8,0,9));
    return 0;
}

Java的Collections类提供了binarySearch方法。事实上C与C++也有二分查找库函数bsearch。
通过二分查找的例子，我们可以发现递归的过程是：

实际上，不使用递归也可以完成这个过程。

int binarySearch(int* arr, int x, int low, int high) {
    while (low <= high) { 
        int mid = (low + high) / 2;
        if (arr[mid] == x) 
            return mid; 
        else if (arr[mid] < x)
            low = mid + 1;
        else 
            high = mid - 1;
    }
    return -1; // 顺序表中不存在待查元素
}
int main(){
    int arr[10] = {1,2,3,4,5,6,7,8,9,10};
    printf("element position: %d", binarySearch(arr,8,0,9));
    return 0;
}

这段代码没有使用递归，但是做的事和递归是一样的。
那么，二分查找的时间复杂度相比于普通的顺序查找如何呢？顺序查找就是将表遍历一遍，有可能第一个就找到，有可能最后一个才找到，所以最坏时间复杂度是O(n)，由于待查找的元素出现在表各个位置的机会相等，因此由等差数列求和公式，平均时间复杂度为O(n)。对于二分查找，可以写出时间复杂度表达式：
$$T(n)=T(\lfloor \frac{n}{2}\rfloor )+\Theta (1)$$由大Θ的定义，可以把Θ(1)换成c：$$T(n)=T(\lfloor \frac{n}{2}\rfloor )+c$$我们将用三种方法来考察它的时间复杂度。

代入法

代入法的思想是:先猜测一个界，然后用数学归纳法证明这个界是正确的。
我们猜测T(n)=O(logn)，下面证明：

这里需要注意，边界条件为什么取了n=2而不是n=1呢？这是因为n=1时，logn=0，这个时候T(1)是不可能小于等于clogn的。所以只能取n=2，也就是说，$T\left(n\right)\le c_{1}logn$对于n≥2成立，由于渐进上界考虑的是n足够大时的性质，因此n=1不符合这个性质完全不重要。

那么问题来了，怎么就能猜到T的上界呢？其实是看经验，说白了就是猜。当你分析过的时间复杂度足够多时，你就大概记住了每种时间复杂度对应什么样的递归表达式。但是既然能猜到了，那就得到结果了呀，因此代入法主要作为证明使用。如果你并不能看出来时间复杂度的上界，想要通过代入法得到答案是几乎不可能的，除非先猜测一个比较宽的界，然后一步一步缩小，但是有这个功夫，用别的方法早就得到了。所以我们来看接下来的方法。

递归树法

我们知道T(n)是1到n层递归所用的总时间代价，它由n以下所有层的的时间代价和本层所做的处理的时间代价相加构成，比如二分查找中1到n层的时间T(n)是取中位数、比较的时间$\Theta \left(1\right)$和下面所有层的时间$T\left(\lfloor \frac{n}{2}\rfloor \right)$相加。这样，如果我们将一层层的递归画成一棵树：
图中，每个结点上标注的是除了递归调用函数之外，本层所做其他处理的时间复杂度，也就是二分查找中取中位数、比较的时间$\Theta \left(1\right)$。由于递归调用其实是把问题交给下一层了，所以每个结点标注的也就是这一层真正做的事的时间代价，总的时间代价就等于所有结点上标注的时间代价之和。比如说我算我这一个月做了什么事，也就是这30天所做的事等于前29天所做的事加上第30天所做的事，前29天所做的事又等于前28天所做的事加上第29天所做的事。这样我们在将一个洋葱一层层剥开时，每一层只算那一层的厚度，最后加起来就是总的整个洋葱的半径，和这个是相同的道理。
由于每次递归调用n都会减半，因此这棵树总共有logn层，每层是c，所以总的时间代价就是clogn，也就是O(logn)。

可能这还不太像一棵树，那么我们考虑这个函数：
$$T(n)=2T(\frac{n}{2})+n$$
这里需要注意，每一层的时间代价都是不一样的，因为每一层的“n”是不一样的，比如到了T(n/2)那一层，后面加的n也要随之变为n/2，也就是T(n/2)=2T(n/4)+n/2。由于每一层之和都是n，总共logn层，因此总时间复杂度是O(nlogn)。

再看这个：$$T\left(n\right)=T\left(\frac{2n}{3}\right)+T\left(\frac{n}{3}\right)+\Theta \left(n\right)$$
递归树画出来是这样的：

这不是一棵满二叉树，每一层上的结点不一定都是长满的。如果一层长满结点，那么这一层结点代价之和是cn，因此实际上每一层上结点的代价之和一定≤cn。最长的一个路径是不断乘以2/3的一条路径，也就是图中最左侧的路径。这条路径的长度是${\log }_{\frac{3}{2}}n$，因此这棵递归树的深度就是${\log }_{\frac{3}{2}}n$。所以总的时间代价不会小于$cn{\log }_{\frac{3}{2}}n$，也就是$T\left(n\right)=O\left(n\log n\right)$.那么可不可以因此确定函数的时间复杂度就是Θ(nlogn)呢？肯定是不可以的，因为nlogn不一定是紧确的。如何得到一个紧确的界呢？这里我们介绍一个定理：

对任意两个函数$f\left(n\right)$和$g\left(n\right)$，我们有$f\left(n\right)=\Theta \left(g\left(n\right)\right)$，当且仅当$f\left(n\right)=O\left(g\left(n\right)\right)$且$f\left(n\right)=\Omega \left(g\left(n\right)\right)$

其实上一篇就应该提到这个定理，但是我忘了
我们考虑树中最短的路径，也就是图中最右侧的路径，这条路就的长度是${\log }_{3}n$，也就是说在树到达这个深度之前，所有结点都是长满的。那么这些长满的结点代价之和是$cn{\log }_{3}n$，也就是说整棵树的结点代价之和肯定不会小于$cn{\log }_{3}n$，即$T\left(n\right)=\Omega \left(n\log n\right)$。由定理，便可得出$T\left(n\right)=\Theta \left(n\log n\right)$

递归树的做法差不多就是这样，但是每次都要画一棵树，也有一点麻烦，有没有更简单的办法呢？这个时候就需要搬出我们的秒杀神器：

主方法

主方法依赖于主定理(master theorem)。将主定理应用于求解问题，就变成了主方法。所以主定理和主方法是一回事。主定理的表述如下：

对于$T\left(n\right)=aT\left(\frac{n}{b}\right)+f\left(n\right)$，

①如果存在ϵ>0，使得$f\left(n\right)=\Omega \left(n^{{\log }_{b}a+ϵ}\right)$，且对于某个常数$c<1$和所有足够大的n有$af\left(\frac{n}{b}\right)\le cf\left(n\right)$，则$T\left(n\right)=\Theta \left(f\left(n\right)\right)$

②如果$f\left(n\right)=\Theta \left(n^{{\log }_{b}a}\right)$，则$T\left(n\right)=\Theta \left(n^{{\log }_{b}a}\log n\right)$

③如果存在ϵ>0，使得$f\left(n\right)=O\left(n^{{\log }_{b}a-ϵ}\right)$，则$T\left(n\right)=\Theta \left(n^{{\log }_{b}a}\right)$

我们来分析一下这一大段话都说了些什么。首先，$T\left(n\right)=aT\left(\frac{n}{b}\right)+f\left(n\right)$，这表明主方法能够应用的场景是有限的，必须要能够将一个问题分解为相同规模的子问题。这里的$\frac{n}{b}$既可以是$\lfloor \frac{n}{b}\rfloor$也可以是$\lceil \frac{n}{b}\rceil$

123三条其实是将f(n)与$n^{{\log }_{b}a}$相比较，根据比较结果的不同，T(n)也不同。①中的“存在ϵ>0，使得$f\left(n\right)=\Omega \left(n^{{\log }_{b}a+ϵ}\right)$”，意思是f(n)比$n^{{\log }_{b}a}$大，大多少呢，至少得大出一个多项式倍，也就是$n^{ϵ}$倍。这就要求不能仅仅大出对数倍（logn倍），例如b=2, a=4，那么$n^{{\log }_{b}a}$就是$n^2$，如果f(n)仅仅是$n^2\log n$，是不满足主方法的条件的。哪怕是$n^{2.000001}$都可以，因为比n大出了$n^{0.000001}$倍，这就叫做f(n)“多项式地大于”$n^{{\log }_{b}a}$。自然，$n^{2.000001}\log n$也可以，但是$n^2\log n$不行，原因是f(n)比$n^{{\log }_{b}a}$大logn倍，这比任何多项式$n^{ϵ}$都要小。③中的条件也是完全同理的，要求f(n)“多项式地小于”$n^{{\log }_{b}a}$。“多项式地“大于或小于只是说“至少大出多项式倍”，并不是说只能大出多项式倍。大出多项式乘对数倍也是可以的。

对于某个常数$c<1$和所有足够大的n有$af\left(\frac{n}{b}\right)\le cf\left(n\right)$，这是仅仅在情况①中对f(n)的限制。这个限制其实多数f(n)都可以满足。只需要把
$af\left(\frac{n}{b}\right)$和$cf\left(n\right)$分别写出来，凑一个c使得不等式成立就可以了。但是注意这句话的意思是要有一个固定的c对于所有n都成立，和“对于所有足够大的n有$af\left(\frac{n}{b}\right)<f\left(n\right)$”不是一个意思。后者$af\left(\frac{n}{b}\right)$可以无限趋近于$f\left(n\right)$，即$\underset{n\to \infty }{\lim }af\left(\frac{n}{b}\right)=f\left(n\right)$，例如下图这种情况，而这是不符合要求的。

怎么记这么长的定理呢？我们在介绍递归树时提到，递归的1到n层所用的总时间T(n)由下面所有层的时间和本层（第n层）所做的处理的时间构成。$aT\left(\frac{n}{b}\right)$是下面所有层的时间，为$\Theta \left(n^{{\log }_{b}a}\right)$。$f\left(n\right)$是本层处理的时间。由于是相加，所以T(n)应该按照两项中大的来算，另一项就被忽略。如果一样大呢，就是两者兼顾，需要乘上一个logn。这里只是为了大家快速记忆以便应用。至于为什么，大家可以看书上第55页的4.6 证明主定理。

特别地对于$f\left(n\right)=n^d$这种特殊形式
①的条件“存在ϵ>0，使得$f\left(n\right)=\Omega \left(n^{{\log }_{b}a+ϵ}\right)$”还可以写成：$a<b^d$
②的条件“存在ϵ>0，使得$f\left(n\right)=\Theta \left(n^{{\log }_{b}a+ϵ}\right)$”还可以写成：$a=b^d$
③的条件“存在ϵ>0，使得$f\left(n\right)=O\left(n^{{\log }_{b}a+ϵ}\right)$”还可以写成：$a>b^d$

下面我们来实战试一试主方法好不好用，该怎么用。

①$T\left(n\right)=9T\left(\frac{n}{3}\right)+n$

首先得到$f\left(n\right)=n$，$a=9$，$b=3$
$n^{{\log }_{b}a}=n^2$，那么f(n)多项式地小于$n^{{\log }_{b}a}$，符合第三种情况，因此$T\left(n\right)=\Theta \left(n^2\right)$

②$T\left(n\right)=3T\left(\frac{n}{4}\right)+n\lg n$

首先得到$f\left(n\right)=n\lg n$，$a=3$，$b=4$
$n^{{\log }_{b}a}=n^{0.792}$，n多项式地大于$n^{{\log }_{b}a}$，因此$f\left(n\right)=n\lg n$多项式地大于$n^{{\log }_{b}a}$。$af\left(\frac{n}{b}\right)=\frac{3}{4}n\lg \frac{n}{4}$，取$c=\frac{3}{4}$，就可以满足对所有足够大的n，$af\left(\frac{n}{b}\right)\le cf\left(n\right)$。因此，满足第一种情况，$T\left(n\right)=\Theta \left(n\log n\right)$。

我们可以看到，对于满足条件的递归表达式，主方法求解的速度远远快于代换法和递归树法。主方法唯一的缺点就是对于递归表达式的形式要求比较严格。当我们拿到一个递归表达式时，先判断是否符合主方法的条件，如果符合，直接用主方法，否则用递归树法，再不行就只能代入法。还可以用换元法等方法，例如令m=logn，算出m的上界后再代入n（见书p49）等等。

本次我们讨论了最基本的采取分治策略的算法——二分查找，并由此引入了递归形式的时间复杂度表达式和它们的三种求解方法。分治策略在算法中应用非常广泛，其他几个经典的分治策略算法将会在接下来的文章中讨论。
（本文基于机械工业出版社《算法导论》第三版，文中如有错误，欢迎指出）

参考文献

[1] (美)科尔曼(Cormen, T.H.)等. 算法导论[M]. 北京: 机械工业出版社, 2013