【MIT算法导论】分治法
前言
本文是B站《算法导论》MIT公开课的随课笔记,关于内容和笔记格式有问题的朋友欢迎私信交流~
部分内容是阅读《算法导论》原著之后进行的补充
分治法和增量方法等均属于算法设计的方法
分治法的优点之一就是可以利用递归式复杂度分析方法,确定算法运行的时间。
一.基础概念
- 分治法的适用条件
对于很多在结构上呈现递归的算法,通常采用分治策略。
递归:为了解决一个给定的问题,算法要一次或多次地递归调用其自身来解决相关的子问题。
-
分治策略的基本思想
将原问题划分成n个规模较小而结构与原问题相似的子问题;
递归地解决这些子问题,再合并其结果,就得到原问题的解。 -
分治模式及其应用
①分治模式在每一层递归上的三个步骤
【分解】:将原问题分解成一系列子问题
【解决】:递归地解决各个子问题;若子问题足够小,可以直接求解
【合并】:将子问题的结果合并成原问题的解
②分治法的应用——归并排序(merge sort)
<归并排序的模式>
【分解】:将n个元素分成各含n/2个元素的子序列
【解决】:用归并排序对两个子序列递归地排序
【合并】:合并两个已排序好的子序列就可以得到排序结果
在对子序列进行排序的过程中,长度为1则递归结束;单个元素被视为是已经排序好的。
<归并排序的分析>
在归并排序中最重要的步骤是【合并】,即将两个有序表合并成一个有序表,为此引入了一个辅助过程merge(A,p,q,r).
<归并的伪码表示>
- 核心思想就是维护两个指针,顺次比较两个有序数组中的元素,将较小的元素放到最终的数组中,再移动指针,直到所有的元素都已经被复制到新的数组中去了。
- 在上述伪码表示,巧妙地引用了哨兵元素(∞),将两个有序数组的末尾都插入一个哨兵元素,可以避免对数组是否为空进行查询判断、防止越界。
<归并的复杂度分析>
因为我们预先知道只有r-p+1个元素会被放到输出堆中去,因此一旦执行了r-p+1个基本步骤后,算法就停止了。
<归并排序的总步骤>
递归地将当前排序任务划分成两个子任务,再进行有序合并。
二.算法分析
- 归并排序的递归式表达
- 递归式复杂度分析
①主定理套用规则
如上图递归式的表达式,该递归式符合主定理应用的第二种情况。
其中k=0,所以可以得到最后T(n)的复杂度就是线性对数级别的。
②递归树分析法
三.常见的分治算法
- 二分查找(binary search)
①算法思路
【分解】:将当前元素和有序数组的中间元素进行比较
【解决】:如果x大于中间元素,在右半边数组中递归查找;如果x小于中间元素,在左半边数组中递归查找;如果x等于中间元素,递归结束。
【合并】:无计算量
②复杂度递归表示
T(n) = T(n/2) + θ(1) = O(logn)
- 乘方问题
①问题描述
给定一个实数x和一个整数n,求解乘方xn的数值
②一般思路
所谓乘方就是连乘,求解xn,就需要对x连乘n或n-1次,问题复杂度为O(n)
③分治策略
我们希望利用分治策略,能够在非线性时间内解决乘方问题。
<思想雏形>
xn = xn/2 * xn/2,先不考虑一些细节问题
将指数n采用分治进行分解,好处在于分解出的子问题规模复杂度减半了,且得到的两个子问题是完全一致的,相当于我们将一个规模为n的问题分解成一个规模为n/2的问题,再加上常数级别的乘法运算量。
<分治模型>
xn = xn/2 * xn/2 ,if n 为偶数
xn = x(n-1)/2 * x(n-1)/2 * x ,if n 为奇数
<复杂度分析>
T(n) = T(n/2) + θ(1) = O(logn)
- 斐波那契数(Fibonacci numbers)
①定义
②递归算法及复杂度分析
int Fibonacci(int n){
if(n == 0)
return 0;
if(n == 1)
return 1;
return Fibonacci(n-1) + Fibonacci(n-2);
}
所谓递归算法,就是每次计算Fn的时候,就会依次调用Fn-1,Fn-2,…
复杂度分析,直觉来看,每次递归的时候会将原问题转换成一个规模变化不太大的子问题,所以定性分析认为复杂度呈指数级增长。
算法复杂度为Ω(φn),其中φ = (1+根号2)/ 5
在算法分析设计中,我们更加倾向于多项式复杂度的算法,而非指数级增长的算法。
③自下而上/动态规划算法
const int maxn = 105;
int Fibonacci(int n){
int dp[maxn];
dp[0] = 0;
dp[1] = 1;
for(int i = 2;i<=n;i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
很显然,在这样的动态规划思想下(当前问题的解收到前几个子问题的解的影响),时间复杂度为O(n),也就是线性复杂度。
优化:当然空间复杂度还可以继续优化,因为每一次问题的解只收到前两个问题状态的解的影响,所以可以只保留两个临时变量进行动态迭代。
这样空间复杂度就从线性变成常数级别。
④logn时间算法
利用一种特殊的矩阵结构,可以将斐波那契数列的求解问题转换成logn的时间复杂度下的矩阵幂乘问题。
证明:
【方法论】对于这样结构的结论,我们常常使用数学归纳法进行证明。
进行归纳时核心还是使用了斐波那契数列的定义式,当n≥2的时候,有Fn = Fn-1 + Fn-2 成立
- 矩阵乘法问题
(1)问题描述
输入:A = [aij],B = [bij];i,j = 1,2,…,n
输出:C = [cij] = A·B
其中,根据矩阵的乘法运算,cij = Σaik·bkj
(2)问题求解
①标准算法 O(n3)
按照矩阵乘法的定义,矩阵的每一个i行j列的元素,都是矩阵A的第i行元素和矩阵B的第j列的元素做相应的点乘运算的结果。
第一层和第二层循环控制A中的行和B中的列;
第三层循环控制向量点乘运算时选取的每个分量元素。
void matrix_multiple(int a[],int b[],int& c[]){
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++){
c[i][j] = 0;
for(int k = 1;k<=n;k++){
c[i][j] += a[i][k]*b[k][j];
}
}
}
}
②分治算法1
将分治法引入到矩阵求解的问题中来,分治法的常用思路就是将一个规模为n的问题分割为规模为n/2的两部分。
那么对于一个nxn的矩阵乘法问题,我们希望把它分解成一个n/2 x n/2 的子矩阵相乘的问题,从而引出分块矩阵的乘积。
按照分块矩阵的定义以及运算规则,就有
r = ae + bg;s = af+bh;t = ce + dg;u = cf + dh
根据分块矩阵的运算规律,就可以得到完成一次矩阵乘法需要8次递归的矩阵乘法以及四次矩阵的加法运算,矩阵的加法运算是平方级别的。
T(n) = 8T(n/2) + θ(n)
根据这个复杂度的递推公式,由主方法的结论,最后这个算法的复杂度依然为立方级别。
③分治算法2----斯特拉森算法
核心思路:对于上面的递归式T(n) = 8T(n/2) + θ(n),我们希望尽可能减少乘法的次数
构造了7个多项式,每个多项式都只进行了一次乘法和常数次加减法,所以每个多项式运算的复杂度是基本一致的。
保持矩阵的乘法及其分块不变:
P1 = a*(f-h)
P2 = (a+b)* h
P3 = (c+d) * e
P4 = d * (g-e)
P5 = (a+d) * (e+h)
P6 = (b-d) * (g+h)
P7 = (a-c) * (e + f)
然后我们的结果矩阵的四个分块就可以由上述矩阵多项式进行表示
r = P5+P4-P2+P6
s = P1 + P2
t = P3+p4
u = P5+P1-P3-P7
算法思路
【分解】:将用于计算的两个矩阵A和B进行分块;计算一些和运算,比如说(f-h),(c+d)等------θ(n2)
【解决】:分别递归地处理乘积,得到P1,P2,…,P7
【合并】:根据Pi(i=1-7)的组合得到结果矩阵的各个分块r,s,t,u。-------θ(n2)
复杂度分析
T(n) = 7T(n/2) + θ(n2)
根据主方法的结论,最后得到的算法复杂度复杂度大约是θ(n2.81)的水平,可以看出该复杂度是多项式地小于立方级别。
后记
-
视频该一节中最后还有一个关于集成电路布局的算法设计,很有意思,而且也可以把分治法、主方法判断复杂度串联起来,也可以学会一种算法优化的思路,因为牵扯到很多作图(因为懒),笔者没有把这一部分笔记整理了,有兴趣的同学可以直接看原视频的讲解。
算法导论-MIT-分治法 -
建议在看那些案例讲解之前一定要先把主方法给弄懂,至少要记住相关结论。