第3 章
分 治 法
3.1 概 念
3.1.1 分治法的基本思想
分治法是这样一种方法:对于一个输入规模为n 的问题,用某种方法把输入分割成k 个
子集(1<k≤n),从而产生k 个子问题,k 个子问题解决后,再用某种方法组合成原来问题
的解。
基本思想:将问题分解成若干个子问题,然后求解子问题,由此得到原问题的解,即“分
而治之”。
分治法是一个递归地求解问题的过程,在每层的递归中应用如下三个步骤。
分解(Divide):将问题划分为一些子问题,子问题的形式与原问题一样,只是规模更小。
解决(Conquer):递归地求解出子问题。如果子问题的规模足够小,则停止递归,直接求解。
合并(Combine):将子问题的解组合成原问题的解。
其过程如图3-1所示。
图3-1 分治法问题求解过程
伪代码实现:
divide-and-conquer(S){
if (small(S)) return(adhoc(S));
divide S into smaller subset S1,S2,…,Si,…Sk;
for(i=1; i<=k; i++)
yi ← divide-and-conquer(Si);
return merge(y1,y2,…,yi,…,yk);
}
第3 章 分治法 51
其中:
small(S)是一个布尔值函数,它判断S的输入规模是否小到无须进一步分治就能算出
其答案。
adhoc(S)是分治法的求解子算法。
merge(y1,y2,…,yi,…,yk)为解的归并子算法。
3.1.2 分治法所处理问题的基本特征
分治法虽然是一种常用的算法但并不适用于所用的问题场景,它所适用的问题应满足
如下几个特征。
(1)该问题的规模缩小到一定的程度就可以容易地解决。
(2)该问题可以分解为若干个规模较小的相同问题。
(3)利用原问题分解的子问题所求出的解,应当可以合并为该问题的解。
(4)各个子问题之间应当是相互独立的。
在以上几个特征中,最为关键的是特征(3),这一特征直接决定该问题能否使用分治算
法。当问题同时满足特征(1)和特征(2)而不满足特征(3)时,依然可以选择动态规划或者贪
心算法来解决这一问题。而特征(4)则与分治算法的效率有关,当子问题之间不相互独立,
使用分治法会做一些不必要的工作,此时,动态规划会是一个更好的选择。
3.1.3 分治算法的实现思路
1.自顶向下的分治思路
此方法是从原问题出发,对原问题进行分解,在每次的分解后,所需要处理的问题相较
于原来的问题规模更小。原问题的可解性依次地传递到下一层,通过依次对问题的处理,保
证了原问题可以得到解决。下面以快速排序算法为例解释这一过程。
快速排序算法的思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记
录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到
整个序列有序。
快速排序算法的每一次的划分,都会使一个元素处于一个正确的位置,其伪代码如下。
Quick_Sort(A,p,r){
//输入: 数组A,起始位置p,终止位置r
//输出: 已排序数字
if(p <r then)
povit =A[p]; //使用子表的第一个值作为枢轴记录
i <-p;
j <-r;
//从表的两端交替地向中间扫描
while i <j do
while i <j And A[j]>povit do
j <-j-1;
if i <j do
i <-i+1;
A[i]=A[j];
52 算法设计与分析
end
end
while i <j And A[j]<=povit do
i <-i+1;
if i <j do
j <-j-1;
A[j]=A[i];
end
end
A[i]<-povit; //枢轴记录保存到最终位置
Quick_Sort(A, p, r-1);
Quick_Sort(A, p+1, r);
end
}
自顶向下的设计思路还同样适用于汉诺塔、二分搜索、线性时间选择等问题。
2.自底向上的分治思路
对于使用分治法处理问题,除了在解决问题的过程中一步一步地将问题的规模缩小的
同时处理问题,考虑到子问题的解的性质,还可以使用向上递推的方式,在已知解的基础上,
解决规模更高的同类问题,最终使得原问题得以解决,这就是自底向上的分治策略。
这一分治策略的使用,较为经典的就是排序算法中的归并排序。在此,以二路归并算法
为例进行说明。
二路归并排序的算法思想:假设初始序列包含n 个记录,则可看成n 个有序的子序列,
每个子序列的长度为1,然后两两归并,得到n/2个长度为2或1的有序子序列;再两两归
并,……,如此重复,直到得到一个长度为n 的有序序列为止。
归并排序的算法实现如下。
MERGE(sourceArr,tempArr,sIndex,midIndex,eIndex){
i =sIndex
j =midIndex+1
k =sIndex
//取出两个有序子序列中最小的一个元素,放入新的有序数列中
while (i! =midIndex+1 and j!=eIndex+1){
if(sourceArr[i]<sourceArr[j]){
tempArr[k]=sourceArr[i];
i++;
}else{
tempArr[k]=sourceArr[j];
}
k++
}
while(i !=midIndex+1){ //前面的有序数列中还有元素
tempArr[k++]=sourceArr[i++];
}
while(j !=eIndex+1){ //后面的有序数列中还有元素
tempArr[k++]=sourceArr[j++];
第3 章 分治法 53
}
//将有序数列复制给原数列
for(m =sIndex to eIndex){
sourceArr[m]=temp[m];
}
} //归一化
MERGESORT(sourceArr,tempArr,sIndex,eIndex){
//类似二分查找,每次取半
if (sIndex <eIndex){
mid =sIndex +(eIndex -sIndex)/2;
MERGESORT(sourceArr,tempArr,sIndex,mid);
MERGESORT(sourceArr,tempArr,mid+1,eIndex);
MERGE(sourceArr,tempArr,sIndex,mid,eIndex);
}
}
3.2 折半查找
3.2.1 问题描述
问题描述:在一个有序序列S 中,查找其中是否包含元素x,如果x 是S 中的元素,需
要获得x 在S 中的位序。
3.2.2 问题分析
通过问题描述可知,带查找的序列S 是一个有序序列,其按照由大到小或由小到大的
顺序排列。
折半查找的思路是:在有序表中,取中间记录作为比较对象,若给定值与中间记录的关
键码相等,则查找成功;若给定值小于中间记录的关键码,则在中间记录的左半区继续查找;
若给定值大于中间记录的关键码,则在中间记录的右半区继续查找。不断重复上述过程,直
到查找成功,或所查找的区域无记录,查找失败。
例如,在一张包含N 个记录的表(K1,K2,…,KN )中,要查找x 是否在表中。折半查找
的思路是,首先将x 与表中间记录的关键词KN/2进行比较,所得到的结果必属于下面3种
图3-2 问题划分
情况之一:K <KN/2、K =KN/2、K >KN/2。若本次查找不成
功,则根据比较结果确定下一次应该在表的“哪一半”中去找,并
对确定的“这一半”重复上述过程。如此进行下去,直到查找成
功,或者直到表的长度为0,查找以失败告终。在进行了至多
log2N 次比较之后,或者找到关键词等于x 的记录,或者确定它
不存在。过程如图3-2所示,其中,mid=(1+N )/2。
3.2.3 问题求解
假设有如图3-3所示序列,要在其中查找值为14的记录。
54 算法设计与分析
图3-3 待查找序列
首先,mid=1+13
2 =7,以14比较K7=31,由于14<K7,查找范围只能在K7 的左侧,
如图3-4所示。
此时mid=1+6
2 =3,以14比较K3=18,由于14<K3,查找范围只能在K3 的左侧,如
图3-5所示。
图3-4 一次查找后待查序列 图3-5 二次查找后待查序列
此时mid=1+2
2 =1,以14比较K1=7,由于14<K1,查找范围只能在K1 的右侧。
比较14和K2=14,K2 即为要查找的元素。
3.2.4 算法实现
折半查找算法递归实现如下。
int BinSearch2(int r[], int low, int high, int x){
//数组r[1]~ r[n]存放查找集合
if (low>high) return 0;
else {
mid=(low+high)/2;
if(x<r[mid])
return BinSearch2(r, low, mid-1,x);
else if(x>r[mid])
return BinSearch2(r, mid+1, high,x);
else return mid;
}
}
折半查找算法非递归实现如下。
int BinSearch2(int r[], int low, int high, int x){
//数组r[1]~ r[n]存放查找集合
if (low>high) return 0;
while(low<=high){
if(r[low].key==x)
return low;
if(r[high].key==x)
return high;
mid=low+(high-low)/2;
if(r[mid].key==x)
第3 章 分治法 55
return mid; //查找成功,返回
if(r[mid].key<x)
low=mid+1; //继续在R[mid+1..high]中查找
else
high=mid-1; //继续在R[low..mid-1]中查找
}
if(low>high)
return 0;
}
3.2.5 折半查找判定树
折半查找的过程可以用二叉树来描述,树中的每个结点对应有序表中的一个记录,结点
的值为该记录在表中的位置。通常称这个描述折半查找过程的二叉树为折半查找判定树,
简称判定树。
判定树的构造过程如下。
(1)当n=0时,折半查找判定树为空。
(2)当n>0时,折半查找判定树的根结点是有序表中序号为mid=1+n
2 的记录,根结
点的左子树是与有序表r[1]:r[mid-1]相对应的折半查找判定树,根结点的右子树是与
r[mid+1]:r[n]相对应的折半查找判定树。
如图3-6所示为一棵折半查找判定树,其中,圆圈为内部结点,为表中位置号;方框为外
部结点,表示不在表中的数据。
图3-6 查找判定树
3.2.6 算法复杂度分析
因为折半查找每查找一次排除掉一半的不适合值,所以对于n 个元素的情况如下。
一次二分后,查找范围剩下:n1=n2
。
两次二分后,查找范围剩下:n2=n
22。
…
m 次二分后,查找范围剩下:nm =n
2m 。
56 算法设计与分析
在最坏情况下是在排除到只剩下最后一个值之后得到结果,即n
2m =1。算法复杂度为
O(log2n)。
3.3 顺序统计
3.3.1 问题描述
在一个由n 个元素组成的集合中,找出第k 小元素(或第k 大元素)。
例如,在一个元素集合中,最小值是第一个顺序统计量(i=1),最大值是第n 个顺序统
计量(i=n)。
3.3.2 问题分析
如果集合中的n 个元素已经排好序,找出第k 小元素(或第k 大元素)显然能够在O(1)
的时间内完成。但要将集合中的n 个元素已经排好序需要O(log2n)的时间代价。
3.3.3 问题求解
下面采用分治法求解顺序统计问题。
(1)首先从原始集合中随机选择一个元素a,以a 为界将原始集合中的元素放入三个
新的集合S1,S2,S3。S1 包含所有比a 小的元素,S2 中只有一个元素a,S3 中包含所有比
图3-7 集合划分
a 大的元素,如图3-7所示。要完成上述过程需要n-1次比较
操作。
(2)假设要找出第k 小的元素,这时判断m =|S1|值的
大小。
① 如果m >k-1,则要寻找的元素在S1 中,在S1 中继续执行步骤(1)。
② 如果m =k-1,则a 就是要找的元素。
③ 如果m <k-1,则要寻找的值在S3 中,这时令k=k-(m +1),在S3 中继续执行步
骤(1)。
3.3.4 算法实现
顺序统计分治法递归实现如下。
int OrderStatistic (int r[], int number){
//数组r[1]~ r[n]存放查找元素集合
n=r.length;
//数组元素个数小于number,第number 小的元素不存在
if (n<number) return 0;
array s1=new array();
array s3=new array();
int k=random()*n+1;
for(i=1;i<=n;i++){
第3 章 分治法 57
if(i==k) continue;
if(r[i]<=r[k])
s1.add(r[i]);
else
s3.add(r[i]);
}
if(s1.length>number-1)
return OrderStatistic(s1,number);
elesif(s1.length==number-1)
return r[k];
else
return OrderStatistic(s3, number-s1.length-1);
}
顺序统计分治法递归实现如下。
int OrderStatistic (int r[], int number){
//数组r[1]~ r[n]存放查找元素集合
n=r.length;
//数组元素个数小于number,第number 小的元素不存在
if (n<number) return 0;
while(true){
array s1=new array();
array s3=new array();
int k=random()*n+1;
for(i=1;i<=n;i++){
if(i==k) continue;
if(r[i]<=r[k])
s1.add(r[i]);
else
s3.add(r[i]);
}
if(s1.length>number-1){
r=s1.copy();
n=s1.length;
continue;
}
elesif(s1.length==number-1)
return r[k];
else{
r=s3.copy();
n=s3.length;
numner=number-s1.length-1;
}
}
}
58 算法设计与分析
3.3.5 算法复杂度分析
1.平均时间复杂性分析
设集合中无相同的元素,a 是从集合S 中选出的随机数,其是S 中第i 小元素,i 取值
范围为1~n。
假设i 以相等的概率取1~n 中的一切值,则i 取1~n 中任意值的概率都为pi=1n
。
用a 把S 划分成S1、S2、S3 共需n-1次比较。
若i<k,则在S3 中继续查找,在n-i 个元素范围内查找。
若i>k,则在S1 中继续查找,在i-1个元素上查找。
若i=k,则a 就是要找的元素。
因此算法的平均时间复杂性为:
T(n)≤n -1+ max k 1n
Σk-1
i=1
T(n -i)+ Σn
i=k+1
{ [ T(i-1)] }
=n -1+ max k 1n
Σn-1
i=n-k+1
T(i)+ Σn
i=k
{ [ T(i)] } (3-1)
可归纳证明:
T(n)≤4cn, 其中,c 为常数
所以算法平均时间复杂性为O(n)。
2.最坏情况下时间复杂性分析
在最坏的情况下,每次a 的选取均为最小值或最大值,这时每一轮操作只能排除一个
元素。其时间复杂性等同于选择排序,即:
T(n)=O(n2)
3.4 大整数乘法
3.4.1 问题描述
在科学计算特别是大规模科学计算中,浮点格式很可能无法满足计算精度的要求,为此
要利用大整数来构造高精度的浮点数据类型,以保证最终输出结果的正确性。
大整数还被用来精确计算,例如,自然对数底数e或圆周率π等常数。
这时大整数无法在计算机硬件能直接表示的范围内进行处理。若用浮点数来表示它,
则只能近似地表示它的大小,计算结果中的有效数字也受到限制。若要精确地表示大整数
并在计算结果中要求精确地得到所有位数上的数字,就必须用软件的方法来实现大整数的
算术运算。
问题:设有两个n 位二进制整数X 和Y,实现二进制整数X 和Y 的乘法。
其中,整数超过计算机硬件能直接表示的范围。
3.4.2 问题分析
可以采用传统方法解决上述问题。
第3 章 分治法 59
将乘数的每一位(由低位至高位)逐个去乘被乘数,每乘一次将乘积与原来的积相加,然
后乘数和乘积移位一步,如此下去直至乘数的最高位运算完即得出结果。这样运算共需n2
次一位乘一位运算、n(n-1)次一位加一位运算和n 次移位,总运算复杂性为O(n2)。
3.4.3 分治法求解问题
图3-8 整数划分
将X 和Y 各分为两段,每段的长为n/2,X 分为a 和b 两
段,Y 分为c 和d 两段,如图3-8所示。
由此得出,X =2n 2a+b,Y=2n 2c+d,X 和Y 的乘积为:
XY = (2n 2a +b) (2n 2c+d ) =2nac+2n2
(ad +cb)+bd
(3-2)
使用该分治方法需要进行4次n/2位的乘法,分析时间复杂度有:
T(1)=1
T(n)=4T n2
.
è .
.
. ÷
+O(n)
ì
.
í ..
.. (3-3)
根据时间复杂度主定理可以计算出:T(n)=O(n2)。
3.4.4 改进的分治法
3.4.3节中分治法的时间效率没有提升,主要问题是经过问题划分,子问题中需要4次
n/2位的乘法进行求解。所以算法的改进从减少n/2位的乘法的角度来思考。
由3.4.3节可知:
XY =2nac+2n2
(ad +cb)+bd (3-4)
将式(3-4)进行变换:
XY =2nac+2n2
(ad -ac+cb-bd +ac+bd)+bd
=2nac+2n2
((a -b)(d -c)+ac+bd)+bd (3-5)
如此一来,只需要进行ac,(a-b)(d-c),bd 三次乘法操作。
算法时间复杂度为:
T(1)=1
T(n)=3T n2
.
è .
.
. ÷
+O(n)
ì
.
í ..
.. (3-6)
T(n)=O(nlog23)≈O(n1.59) (3-7)
3.5 最大子数组问题
3.5.1 问题描述
给定一个数组x[1…n],对于任意一对数组下标为p、q(p≤q)的非空子数组,其和记
为S(p,q)=Σq
i=p
x[i],求出S(p,q)的最大值。
60 算法设计与分析
例如,给定数组[-2,1,-3,4,-1,2,1,-5,4],其连续最大子数组和为:S(4,7)=[4,
-1,2,1]=6。
3.5.2 算法分析
根据问题描述,数组元素可以为正数、负数和零。如果采用枚举法求解该问题,需要列
出数组x 的所有连续子数组,共有M 个这样的子数组。
M =Σn
i=1 (n -i+1)=Σn
j=1
j=n(n +1)
2 =O(n2) (3-8)
其中,i 为子数组长度。所以枚举法的时间复杂度为O(n2)。
3.5.3 分治法求解最大子数组问题
下面用分治法求解该问题。首先将数组x[1…n]进行划分,划分为x[1…n/2]和x
n2
+1…n é
. êê
ù
. úú
两个子数组。
假设已求解得出:x[1…n/2]的最大子数组为S1,x n2
+1…n é
. êê
ù
. úú
的最大子数组为S2。
下面要合并子问题的解为原问题的解,有以下3种情况。
(1)数组[1…n/2]的最大子数组即为原问题的最大子数组。
(2)数组x n2
+1…n é
. êê
ù
. úú
的最大子数组即为原问题的最大子数组。
(3)原问题的最大子数组跨越了子问题,假设这时解为S3。
所以原问题的解S 为:
S =max(S1,S2,S3) (3-9)
其中,S1,S2 已知,现在的问题是如何求S3。
可以采用逐步累加的方法:从中间位置开始,分别向左和向右两个方向进行操作,通过
累加找到两个方向的最大和,分别为l_max和r_max,因此存在于中间的最大和为l_max
图3-9 逐步累加求解S3
和(l_max+r_max)。
如图3-9所示,l_max=4,r_max=-1+2+1=2,S3
=l_max+r_max=4+2=6。又因为S1=4,S2=4,所以:
S =max(S1,S2,S3)=max(4,4,6)=6
3.5.4 算法实现
int Divide(int *array,int p,int q){ //array 为输入数组,p 为数组起始位置,
//q 为数组结束位置
if(p==q) //只有一个元素时,返回该元素
return array[p];
else{
int m=(p+q)/2;
int S1=MIN,S2=MIN,S3=MIN; //MIN 为数组array 中最小值或足够小的值
S1=Divide(array,p,m); //左边和的最大值
S2=Divide(array,m+1,q); //右边和的最大值
S3=MiddleMax(array,p,q,m); //中间和的最大值
第3 章 分治法 61
//返回三个值中最大的一个
if(S1>=S2 &&S1>=S3)
S1;
else if(S2>=S1 && S2>=S3)
return S2;
else
return S3;
}
}
求解S3:
int MiddleMax(int *array,int p,int q,int m){
int l_max=MIN,r_max=MIN; //分别用于记录左、右方向累加的最大和
int i;
int sum; //用于求和
sum=0;
for(i=m;i>=p;i--){ //中线开始向左寻找
sum+=array[i];
if(sum>l_max)
l_max=sum;
}
sum=0;
for(i=m+1;i<q;i++){ //中线开始向右寻找
sum+=array[i];
if(sum>r_max)
r_max=sum;
}
return (l_max+r_max); //返回左右之和
}
3.5.5 算法复杂性分析
求解原问题的时间复杂度等于求解S1、S2、S3 的时间之和。设求解原问题的时间复杂
度为T(n),则求解S1、S2 的时间复杂度均为T(n/2)。
求解S3 的时间等于从中间元素向左右扩展元素的个数,在最坏的情况下,向左右扩展
到全部数组元素,所以求解S3 的最坏情况下的时间复杂度为n,所以:
T(n)=2T n2
.
è .
.
. ÷
+n, 当n =1时,T(n)=1 (3-10)
因此,
T(n)=O(nlog2n) (3-11)
3.6 矩阵乘法
3.6.1 问题描述
矩阵乘法作为一种基本的数学运算,在计算机科学领域有着非常广泛的应用。同样地,
在数据处理中,矩阵计算有着无比的优势,矩阵的计算广泛应用于大数据、机器学习等场景。
62 算法设计与分析
在数学中,矩阵(Matrix)是一个按照长方形阵列排列的复数或实数集合。而在计算机
中,矩阵的存储可以由一个二维数组来进行存储。
矩阵相乘最重要的方法是一般矩阵乘积,只有在第一个矩阵A 的列数和第二个矩阵
B 的行数相同时才有意义。矩阵乘法定义为:
设存在矩阵A 和B 分别为m ×p 和p×n 的矩阵,存在尺度为m ×n 的矩阵C,C 中第
i 行、第j 列的元素满足:
Cij =(AB)ij =Σp
k=1
aikbkj =ai1b1j +ai2b2j + … +aipbpj (3-12)
如果m =p=n,这时有:
Cij =(AB)ij =Σn
k=1
aikbkj =ai1b1j +ai2b2j + … +ainbnj (3-13)
本问题是:设A、B 是两个n×n 的矩阵,求解C=A×B。
3.6.2 问题分析
通过式(3-13)可知,求解矩阵C 的每个元素需要n 次乘法和n-1次加法,又由于矩阵
C 共有n×n 个元素,因此两个n×n 矩阵相乘需要O(n3)次乘法和O(n3)次加法。其时间
复杂度是O(n3)的。
3.6.3 分治法求解矩阵相乘
假定n 为2的幂,计算两个n×n 矩阵相乘C=A×B 时,采用分治法,先将每个n×n
矩阵划分为四个n2
×n2
矩阵,再求矩阵的积。
A =
A11 A12
A21 A22
é
. êê
ù
. úú
, B =
B11 B12
B21 B22
é
. êê
ù
. úú
(3-14)
则:
C =
C11 C12
C21 C22
é
. êê
ù
. úú
=
A11 A12
A21 A22
é
. êê
ù
. úú
×
B11 B12
B21 B22
é
. êê
ù
. úú
(3-15)
有:
C11 =A11 ×B11 +A12 ×B21 (3-16)
C12 =A11 ×B12 +A12 ×B22 (3-17)
C21 =A21 ×B11 +A22 ×B21 (3-18)
C22 =A21 ×B12 +A22 ×B22 (3-19)
每个公式对应两对n2
×n2
矩阵的乘法及一个n2
×n2
积的加法。其中,加法操作次数为
4×n2
4。
算法的时间复杂度为:
T(n)=
b n ≤2
8T n2
.
è .
.
. ÷
+cn2 n >2
ì
.
í ..
.. (3-20)
第3 章 分治法 63
其中,b 为常数,8T n2
.
è .
.
. ÷
是8个n2
×n2
相乘,cn2 是加法的运算时间。因此
T(n)=O(n3) (3-21)
我们可以利用这些公式设计的原理设计一个简单的递归分治算法。
3.6.4 Strassen 算法实现矩阵乘法
Strassen算法也是基于分治思想的一种实现矩阵乘法的算法,其基本目标是减少子问
题的矩阵相乘个数,该方法在大规模数值计算中有着广泛的应用。Strassen 算法是由
VolkerStrassen提出的,在矩阵较大时运行速度快于传统算法的矩阵相乘算法。
Strassen算法包含以下4个步骤。
(1)按式(3-15)将输入矩阵A、B 和输出矩阵C 分解为n2
×n2
的子矩阵。
(2)构造和计算中间变量。
P =(A11 +A22)(B11 +B22) (3-22)
Q =(A21 +A22)B11 (3-23)
R =A11(B12 -B22) (3-24)
S =A22(B21 -B11) (3-25)
T =(A11 +A12)B22 (3-26)
U =(A21 -A11)(B11 +B12) (3-27)
V =(A12 -A22)(B21 +B22) (3-28)
(3)由中间变量构造问题的解。C
11 =P +S +T +V (3-29)
C12 =R +T (3-30)
C21 =Q +S (3-31)
C22 =P +R +Q +U (3-32)
(4)时间复杂度分析。Strassen算法子问题求解共计需要7次n2
×n2
相乘、O(n2)次加
法,其时间复杂度为:
T(n)=
O(1), n =1
7T n2
.
è .
.
. ÷
+O(n2), n >1
ì
.
í ..
.. (3-33)
计算可得:
T(n)=O (nlog72
)
3.7 递归式求解
3.7.1 问题描述
用分治法求解问题,分析其算法时间复杂度时,经常用递归式进行表示。例如,对n 个
元素进行归并排序,归并排序采取分治策略,将待排序的n 个元素分为两组,当组内元素无
64 算法设计与分析
序时则继续分组,若组内元素有序,将两组合并,直到所有待排序元素有序。讨论归并排序
的时间复杂度,每次分组都将问题的规模缩小为原来的12
,且一次合并的时间复杂度为
O(n),则可以得到下面的递归式。
T(n)=2T n2
.
è .
.
. ÷
+cn (3-34)
可以用更广义的方式来定义递归式:
T(n)=aT n
b
.
è .
.
. ÷
+f(n) (3-35)
其中,a≥1,b>1,表示将规模为n 的问题分解为a 个规模为nb
的子问题,求解每个子问题
花费时间T n
b
.
è .
.
. ÷
,f(n)是渐近正函数,包含问题分解和子问题合并所需的代价。
递归式描述了一种算法的运行时间,递归式的求解问题不是给定n 的值来求解T (n)
的值的过程,而是计算求解T(n)所要花费的时间代价的问题(解是关于n 的函数)。
3.7.2 代入法求解递归式
代入法是一种假设演绎方法,即先根据经验猜测解的形式,再使用数学归纳法证明解的
正确性。
由于我们知道归并排序的时间复杂度是O(nlgn),所以假设递归式(3-34)的解有上界
T(n)=O(nlgn),即选择常数c>0,有T(n)≤cnlgn,根据数学归纳法,假设此上界对所有
正数m <n 都成立,对于m = n2
也成立,有
T n2
.
è .
.
. ÷
≤c n2
lg n2.
è .
.
. ÷
(3-36)
将公式(3-36)代入递归式(3-34)中,有
T(n)≤2c n2
lg n2
.
è .
.
. ÷
+n ≤cnlgn2
.
è .
.
. ÷
+n
=cnlgn -cnlg2+n
=cnlgn -cn +n ≤cnlgn s.t.(c ≥1) (3-37)
在上述证明中,仅需保证当n 足够大时假设成立即可,渐进函数仅要求我们对n≥n0
时证明T(n)≤cnlgn,其中,n0 是可以选择的常数。事实上,对于边界条件T (1)我们的假
设不成立。
代入法需要我们对解的形式给出正确的猜测,但是并不存在通用的方法来猜测递归式
的正确解,经常需要依靠经验。例如,对于递归式
T(n)=2T n2
+1 .
è .
.
. ÷
+n (3-38)
形式上与递归式(3-34)非常相似,只是在等式右边T 的参数中多加了1。当n 足够大
时n2与n2
+1基本没有区别,所以我们猜测T(n)=O(nlgn),通过数学归纳法仍然可以
证明解是正确的。
第3 章 分治法 65
在实际中,可以首先证明递归式较为宽松的上界和下界,然后不断缩小解的范围,直到
收敛到渐近紧确界T(n)=O(nlgn)。
3.7.3 递归树法求解递归式
递归树可以通过建立递归调用与结点之间的联系来很好地展现递归过程,是描述递归
算法的良好工具。
使用代入法可以简洁地证明一个解是递归式的正确解,但有些时候递归式的正确解往
往难以猜测,这时可以通过绘制递归树来生成一个好的猜测,然后使用代入法来验证猜测的
正确性。
递归树是迭代过程的一种图像表述。递归树往往被用于求解递归方程,它的求解表示
比一般的迭代会更加简洁与清晰。递归树上所有项恰好是迭代之后产生和式中的项,递归
树的生成过程与迭代过程一致,对递归树上的项求和就是迭代后方程的解。
在递归树中,每一个结点表示一个单一子问题的代价,子问题对应某次递归函数调用,
我们将递归树中每层的代价求和,得到每一层的代价,将所有层的代价求和,得到递归调用
的总代价。其生成过程如下。
(1)初始:递归树只有根结点,其值为W (n)。
(2)不断继续下述过程。
① 将函数项叶结点的迭代式W (m )表示成二层子树。
② 用该子树替换该叶结点。
(3)继续递归树的生成,直至树中无函数项(只有初值)为止。
图3-10 顶层递归树
下面绘制递归式(3-34)对应的递归树。
图3-10绘制了一次递归调用对应的递归树,顶层结点cn 代
表递归调用顶层的代价,并将规模为n 的问题分解为两个规模
为n2
的问题。图3-11 中绘制了继续进行递归调用得到的递
归树。
图3-11将图3-10中代价为T n2
.
è .
.
. ÷ 的结点进一步扩展,问题被进一步分解,递归树前两
层的代价之和均为cn,将递归树的所有结点不断扩展,可以得到一棵完整的递归树,如
图3-12所示。
图3-11 二层递归树 图3-12 问题递归树
随着递归调用的进行,问题的规模不断缩小,最终子问题的规模变为1,即原问题被分
66 算法设计与分析
解为n 个规模为1的子问题。每一层的代价之和均为cn,深度为i 的结点对应问题规模为
n 2i (i=0,1,2,…,lgn)。当n
2i =1时,有i=lgn,因此递归树有lgn+1层,整棵树的代价为
cnlgn。
3.7.4 主方法求解递归式
主方法可以直接求出绝大多数递归式的解而无须进行复杂的运算,主方法依赖于下面
的主定理。
令a≥1和b>1是常数,f(n)是一个函数,T(n)是定义在非负整数上的递归式:
T(n)=aT n
b
.
è .
.
. ÷
+f(n) (3-39)
其中,我们将n
b 解释为n
b 和n
b ,那么T(n)有如下的渐近界。
(1)若存在常数ε>0满足f(n)=O (nloga b-ε ) ,则T(n)=Θ (nlogab
) 。
(2)若f(n)=Θ (nlogab
) ,则T(n)=Θ (nloga blgn) 。
(3)若存在常数ε>0满足f(n)=Ω (nloga b+ε ) ,且对某个常数c<1和足够大的n 有a
f n
b
.
è .
.
. ÷
≤cf(n),则T(n)=Θ(f(n))。
主方法将T(n)的解分为三种情况,直观上理解,我们将函数f(n)和函数nlogab
进行比
较,两个函数较大者决定了递归式的解。若nlogab
更大,则属于情况(1),解为T (n)=
Θ (nlogab
) ,若函数f(n)更大,则属于情况(3),解为T (n)=Θ (f(n))。若两个函数大小相
当,则属于情况(2),解需要乘以一个对数因子,解为T(n)=Θ (nloga blgn) 。
除此之外,在第一种情况中,f(n)小于nlogab
是多项式意义上的小于,即f(n)渐近小于
nlogab
,还需要相差一个因子nε。在第三种情况中,还需要满足条件af n
b
.
è .
.
. ÷
≤cf(n)。
主方法并不适用于全部的递归式,f(n)可能小于nlogab
,但不是多项式意义上的小于,
f(n)可能大于nlogab
,但同样不是多项式意义上的大于。所以情况(1)和情况(2)之间存在间
隙,情况(2)和情况(3)之间同样存在间隙,如果函数f(n)落在两个间隙中,或者f(n)不满
足af n
b
.
è .
.
. ÷
≤cf(n),就不能使用主方法求解。
下面通过具体例子来分析主方法的实际应用。
(1)T(n)=9T n3
.
è .
.
. ÷
+n,其中,a=9,b=3,f(n)=n,因此求得nlogab
=n2,有ε=1使得
f(n)=O (nloga b-ε ) ,满足主定理情况(1),从而得到解T(n)=Θ(n2)。
(2)T(n)=T 2n
3
.
è .
.
. ÷
+1,其中,a=1,b=23
,f(n)=1,因此求得nlogab
=n0=1,f(n)=
Θ nlogab
( ) =Θ(1),满足主定理情况(2),从而得到解T(n)=Θ(lgn)。
第3 章 分治法 67
(3)T(n)=3T n4
.
è .
.
. ÷
+nlgn,其中,a=3,b=4,f(n)=nlgn,因此求得nlogab
=nlog34
,由于
f(n)=Ω (nlog34
+ε),其中,ε=1-log34
。且当n 足够大时af n
b
.
è .
.
. ÷
=3n
4lg n4
.
è .
.
. ÷
≤34
nlgn=
34
f(n),则当c=34
时,满足主定理情况(3),可以得到递归式的解为T(n)=Θ(nlgn)。
(4)T(n)=2T n2
.
è .
.
. ÷
+nlgn,其中,a=2,b=2,f(n)=nlgn,因此求得nlogab
=nlog22 =n,
但对于任意的ε>0有f(n)
nlogab
=lgn<nε,因此不存在常数ε>0满足f(n)=Ω (nloga b+ε ) ,故此
递归式不能使用主方法解决。
3.8 证明主定理
3.7节中采用三种方法求解递归式,其中包括主方法。主方法求解递归式依赖于主定
理,本节将证明主定理。
3.8.1 主定理
在此,重复描述3.7.4节中的主定理内容。
令a≥1和b>1是常数,f(n)是一个函数,T(n)是定义在非负整数上的递归式:
T(n)=aT n
b
.
è .
.
. ÷
+f(n) (3-40)
其中,n 是问题规模大小;a 是原问题的子问题个数;n
b 是每个子问题的大小,这里假设每个
子问题有相同的规模大小;f(n)是将原问题分解成子问题和将子问题的解合并成原问题的
解的时间。
我们将n
b 解释为n
b 和n
b ,那么T(n)有如下的渐进界。
(1)若存在常数ε>0满足f(n)=O (nloga b-ε ) ,则T(n)=Θ (nlogab
) 。
(2)若f(n)=Θ (nlogab
) ,则T(n)=Θ (nloga blgn) 。
(3)若存在常数ε>0满足f(n)=Ω (nloga b+ε ) ,且对某个常数c<1和足够大的n 有af
n
b
.
è .
.
. ÷
≤cf(n),则T(n)=Θ(f(n))。
3.8.2 主定理递归树表示
主定理可以用3.7.3节中的递归树进行表示,如图3-13所示。
树的深度为logbn,加上根结点共计logbn+1层,叶子结点数为alogbn 。第i 层共有ai
个子问题,每个问题规模为n
bi 。
68 算法设计与分析
图3-13 主定理递归树
3.8.3 主定理证明
为了便于分析假定n 是b 的幂次,即n=bm ,m 为正整数,m =logbn。
1.对n 为b 的幂主定理证明
假设n 是b 的幂次,即n=bm ,m 为正整数,m =logbn。
引理3.1:令a≥1,b>1是常数,f(n)是一个定义在b 的幂上的非负函数。T (n)是定
义在b 的幂上的递归式:
T(n)=
Θ(1), n =1
aT n
b
.
è .
.
. ÷
+f(n), n =bi
ì
.
í ..
.. (3-41)
其中,i 是正整数,那么
T(n)=Θ (nlogba ) + Σ logbn-1
j=0
ajf
a
bj
.
è ..
. ÷
(3-42)
证明:
由图3-13可知,在层次i 的运算量为f
n
bi
.
è .
.
. ÷ ×ai,则T(n)为:
T(n)=Θ (alogbn ) =Θ (nlogba ) + Σ logbn-1
j=0
aj ×f
n
bj
.
è .
.
. ÷
等式成立。
注:alogbn =nlogba 的证明可根据对数运算公式,也可直接在等式两端求以b 为底的对数
进行证明。
由公式(3-42)可知,T(n)由两部分组成,Θ (nlogba ) 为求解叶结点的代价,Σ logbn-1
j=0
ajf
a
bj
.
è .
.
. ÷
为
分解子问题和合并子问题解的代价。
引理3.2:令a≥1,b>1是常数,f(n)是一个定义在b 的幂上的非负函数。g(n)是定
义在b 的幂上的递归式:
g(n)= Σ logbn-1
j=0
aj ×f
n
bj
.
è .
.
. ÷
(3-43)
对b 的幂,g(n)有如下渐进界。
第3 章 分治法 69
(1)若对某个常数ε>0有f(n)=O (nloga b-ε ) ,则g(n)=O (nlogab
) 。
(2)若f(n)=Θ (nlogab
) ,则g(n)=Θ (nloga blgn) 。
(3)若对某个常数c<1和所有足够大的n 有af n
b
.
è .
.
. ÷
≤cf(n),则g(n)=Θ(f(n))。
证明:
(1)对于情况1,有f(n)=O (nloga b-ε ) ,则:
f
n
bj
.
è .
.
. ÷
=O n
bj
.
è .
.
. ÷
logab
. -ε
è .
.
. ÷
因此,
g(n)= Σ logbn-1
j=0
aj ×f
n
bj
.
è .
.
. ÷
= Σ logbn-1
j=0
aj ×O n
bj
.
è .
.
. ÷
logab
. -ε
è .
.
. ÷
=O
.
è.nlogab
-ε × Σ logbn-1
j=0
abε
blogab
.
è .
.
. ÷
j
=O
.
è.nlogab
-ε × Σ logbn-1
j=0 (bε)j .
. ÷
=O
.
è.nlogab
-ε × bεlogbn -1 bε -1
.
è .
.
. ÷
.
. ÷
=O
.
è.nlogab
-ε × nε -1 bε -1
.
è .
.
. ÷
.
. ÷
(3-44)
由于b 和ε 是常数,因此
g(n)=O
.
è.nlogab
-ε × nε -1 bε -1
.
è .
.
. ÷
.
. ÷
=O
.
è.nlogab
.
. ÷
(3-45)
因此对情况1成立。
(2)对于情况2,假定f(n)=Θ (nlogab
) ,有:
f
n
bj
.
è .
.
. ÷
=Θ
.
è .
n
bj
.
è .
.
. ÷
logab
.
. ÷ (3-46)
代入公式(3-43),得到:
g(n)= Σ logbn-1
j=0
aj ×f
n
bj
.
è .
.
. ÷
= Σ logbn-1
j=0
aj ×Θ n
bj
.
è .
.
. ÷
logab
.
è .
.
. ÷
=Θ Σ logbn-1
j=0
aj × n
bj
.
è .
.
. ÷
logab
.
è .
.
. ÷
=Θ nlogab
× Σ logbn-1
j=0
aj × 1
blogab
.
è .
.
. ÷
. j
è .
.
. ÷
=Θ
.
è.nlogab
× Σ logbn-1
j=0 1.
. ÷
=Θ (nlogab
×logbn) =Θ (nlogab
×lgn) (3-47)
因此对情况2成立。
(3)对于情况3,由于af n
b
.
è .
.
. ÷
≤cf (n),所以f n
b
.
è .
.
. ÷
≤c
af (n),进而f
n
bj
.
è .
.
. ÷
≤ c
a
.
è .
.
. ÷
j
f(n),代入公式(3-43),得到:
g(n)= Σ logbn-1
j=0
aj ×f
n
bj
.
è .
.
. ÷
≤ Σ logbn-1
j=0
aj × c
a
.
è .
.
. ÷
j
f(n)+O(1)
=f(n)Σ logbn-1
j=0
cj +O(1)=f(n) 1
1-c +O(1)=O(f(n)) (3-48)
因此对情况3成立。