算法设计与分析课件.ppt

,第一章 算法概述,第二章 递归与分治策略,第三章 动态规划,第四章 贪心算法,第五章 回朔法,第六章 分支限界法,第七章 概率算法,算法设计与分析 目录,1,第一章 算法概述第二章 递归与分治策略第三章 动态规划,算法设计与分析 递归与分治,2.1 递归的概念,直接或间接地调用自身的算法称为递归算法。由分治法产生的子问题往往是原问题的较小模式，为使用递归技术提供了方便。反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解，自然导致递归过程的产生。,2,算法设计与分析 递归与分治2.1 递归的概念直接或间接地,算法设计与分析 递归与分治,相关概念当子问题足够大,需要递归求解时,称为递归情况;当子问题足够小时,不再需要递归时,递归进入“触底”,进入基本情况;用函数自身给出定义的函数称为递归函数;递归式是一个等式或不等式,它通过更小的输入上的函数值来描述一个函数.,3,算法设计与分析 递归与分治相关概念3,递归函数的内部执行过程,（1）运行开始时，为递归调用建立一个工作栈，其结构包括实参、局部变量和返回地址；（2）每次执行递归调用之前，把递归函数的实参和局部变量的当前值以及调用后的返回地址压栈；（3）每次递归调用结束后，将栈顶元素出栈，使相应的实参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行,算法设计与分析 递归与分治,4,递归函数的内部执行过程（1）运行开始时，为递归调用建立一个,算法设计与分析 递归与分治,例2-3 Ackerman函数当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。Ackerman函数A(n，m)定义如下：,该变量是由函数自身定义,5,算法设计与分析 递归与分治例2-3 Ackerman函数,分析:A(n,m)的自变量m的每一个值都定义了一个单变量函数：M=0时，A(n,0)=n+2M=1时 A(1,1)=2 和 A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，故A(n,1)=2*n(上式是一个递推公式，每当n-1便加2）M=2时，A(1,2)=A(A(0,2),1)=A(1,1)=2 A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，故A(n,2)=2n。M=3时，类似的可以推出M=4时，A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数。,算法设计与分析 递归与分治,6,分析:算法设计与分析 递归与分治6,算法设计与分析 递归与分治,1、证明 A(1,1)=2因为n,m=1使用递推式（4）得 A(1,1)=A(A(0,1),0)由A(0,m)=1,故 A(1,1）=A(1,0)由（1）式 A(1,0)=2 所以A(1,1)=2,2、证明A(n,1)=2n(n=1)因为n,m=1 使用递归式(4)得A(n,1)=A(A(n-1,1),0)由公式(3)A(n,1)=A(n-1,1)+2由此式看出m=1 时，n每降一阶就增加2，一直降到n=1 即A(1,1)共增加n个2，n 个2相加和为2n所以A(n,1)=2n,7,算法设计与分析 递归与分治1、证明 A(1,1)=22、证,算法设计与分析 递归与分治,3、证明当m=2时 A(n,2)=2n由递推式(4)A(n,2)=A(A(n-1,2),1),此时已经演变为m=1的情况，式中A(n-1,2)相当于2节中的n的位置，因此利用2节的结论有 A(n,2)=2A(n-1,2)可以看出随着n的降阶会增长2的倍数，那么当n降为1时即A(1,2)的情况如何呢？根据递推式(4)有A(1,2)=A(A(0,2),1),再由公式(2)A(0,m)=1故A(1,2)=A(1,1)=2所以A(n,2)随着n的降阶每次乘2，共乘n次得A(n,2)=2n公式得证,8,算法设计与分析 递归与分治3、证明当m=2时 A(n,2),定义单变量的Ackerman函数A(n)为：A(n)=A(n,n)。定义其拟逆函数(n)为：(n)=minkA(k)n。即(n)是使nA(k)成立的最小的k值。(n)在复杂度分析中常遇到。对于通常所见到的正整数n，有(n)4。但在理论上(n)没有上界，随着n的增加，它以难以想象的慢速度趋向正无穷大。,算法设计与分析 递归与分治,9,定义单变量的Ackerman函数A(n)为：算法设计与分析,递归树,T(n)=3T(n/4)+O(n 2),算法设计与分析 递归与分治,10,递归树T(n)=3T(n/4)+O(n 2)算法设,算法设计与分析 递归与分治,11,算法设计与分析 递归与分治11,补充：主方法（定理）,求解这类递推式的方法是主方法，主方法依赖于下面的主定理，使用主定理可直接得到递推式的解。定理（主定理）：a1且b1是常数，f(n)是一个函数，T(n)由如下的递推式定义：T(n)=aT(n/b)+f(n)，式中，n/b指n/b或n/b，则T(n)有如下的渐近界：（1）若对于某常数0，有f(n)=O(nlogba-)，则T(n)=(nlogba)；（2）若f(n)=(nlogba)，则T(n)=(nlogbalogn)；（3）若对于某常数0，有f(n)=(nlogba+)，且对于某个常数c1和所有足够大的n，有af(n/b)cf(n)，则T(n)=(f(n)。,T(n)=aT(n/b)+f(n),算法设计与分析 递归与分治,12,补充：主方法（定理）求解这类递推式的方法是主方法，主方法依赖,定理（主定理）：a1且b1是常数，f(n)是一个函数，T(n)由如下的递推式定义：T(n)=aT(n/b)+f(n)，式中，n/b指n/b或n/b，则T(n)有如下的渐近界：（1）若对于某常数0，有f(n)=O(nlogba-)，则T(n)=(nlogba)；,举例：,T(n)=16T(n/4)+n,T(n)=aT(n/b)+f(n),算法设计与分析 递归与分治,13,定理（主定理）：a1且b1是常数，f(n)是一个函数,定理（主定理）：a1且b1是常数，f(n)是一个函数，T(n)由如下的递推式定义：T(n)=aT(n/b)+f(n)，式中，n/b指n/b或n/b，则T(n)有如下的渐近界：（2）若f(n)=(nlogba)，则T(n)=(nlogbalogn)；,举例：,T(n)=T(3n/7)+1,T(n)=aT(n/b)+f(n),算法设计与分析 递归与分治,14,定理（主定理）：a1且b1是常数，f(n)是一个函数,定理（主定理）：a1且b1是常数，f(n)是一个函数，T(n)由如下的递推式定义：T(n)=aT(n/b)+f(n)，式中，n/b指n/b或n/b，则T(n)有如下的渐近界：（3）若对于某常数0，有f(n)=(nlogba+)，且对于某个常数c1和所有足够大的n，有af(n/b)cf(n)，则T(n)=(f(n)。,举例：,T(n)=3T(n/4)+nlogn,T(n)=aT(n/b)+f(n),算法设计与分析 递归与分治,15,定理（主定理）：a1且b1是常数，f(n)是一个函数,递归小结,优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。,缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。,算法设计与分析 递归与分治,16,递归小结优点：结构清晰，可读性强，而且容易用数学归纳法来证明,解决方法：在递归算法中消除递归调用，使其转化为非递归算法。1、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。2、用递推来实现递归函数。3、通过变换能将一些递归转化为尾递归，从而迭代求出结果。后两种方法在时空复杂度上均有较大改善，但其适用范围有限。,算法设计与分析 递归与分治,17,解决方法：在递归算法中消除递归调用，使其转化为非递归算法。算,尾递归是在递归调用时“积累”之前调用的结果，并将其传入下一次递归调用中,将递归方法中的需要的“所有状态”通过方法的参数传入下一次调用中.,算法设计与分析 递归与分治,尾递归只会占用恒量的内存,形式上只要最后一个return语句是单纯函数就可以,18,尾递归是在递归调用时“积累”之前调用的结果，并将其传入下一次,2.2分治法的基本思想,算法设计与分析 递归与分治,将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,19,2.2分治法的基本思想算法设计与分析 递归与分治将一个规模,算法设计与分析 递归与分治,20,子问题1 子问题1的解 子问题2的解 子问题2,算法设计与分析 递归与分治,问题（N个输入）,相同类型,合并解,分治法要求分解成同类子问题，并允许不断分解，使问题规模逐步减小，最终可用已知的方法求解足够小的问题。,21,算法设计与分析 递归与分治问题（N个输入）子问题1子问题2,算法设计与分析 递归与分治,举例：二路归并排序,分解过程：对任意长度为n的序列排序，首先将问题不断分解，直至问题可直接求解。长度为n的序列分解为2个n/2的子序列，依次循环，直至分解为n个长度为1的序列，显然长度为1的序列是有序表。合并过程：将已排序的的子序列不断合并，形成长度为n的排序序列。然后反复进行两两归并为n/2个有序表；再对n/2个有序表两两归并，循环直到得到长度为n的有序线性表。,22,算法设计与分析 递归与分治举例：二路归并排序分解过程：对任,算法设计与分析 递归与分治,template void MergeSort(Type a,int left,int right)if(leftright)/至少有2个元素 int i=(left+right)/2;/取中点 MergeSort(a,left,i);/对前半部分排序 MergeSort(a,i+1,right);/对后半部分排序 Merge(a,b,left,i,right);/合并到数组b Copy(a,b,left,right);/复制回数组a,合并步，将有序表aleft,i和ai+1,right合并到bleft,right,问题分解：规模为原来的一半；问题性质不变。,23,算法设计与分析 递归与分治template class,template void MergeSort(Type a,int left,int right)if(leftright)int i=(left+right)/2;MergeSort(a,left,i);MergeSort(a,i+1,right);Merge(a,b,left,i,right);Copy(a,b,left,right);,分析：二路归并排序的时空复杂性,算法设计与分析 递归与分治,时间复杂度T(n)cT(n/2)T(n/2)O(n)O(n),void Merge(Type c,Type d,int i,int m,int r)int la,lb,lc;la=i;lb=m+1;lc=i;while(la=m,24,template 分析：二路归并,二路归并排序算法存在以下递推式：,解此递归方程，二路归并排序的时间复杂度是O(nlogn)。二路归并排序其空间复杂性为O(n)。,算法设计与分析 递归与分治,25,二路归并排序算法存在以下递推式：解此递归方程，二路归并排序的,算法设计与分析 递归与分治,总结：分治法的适用条件,分治法所能解决的问题一般具有以下特征：该问题规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同子问题，即该问题具有最优子结构性质；利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。,应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用。,关键特征，能否利用分治法完全取决于问题是否具有第四条特征，如果具备了第一条和第二条特征，而不具备第四条特征，则可以考虑贪心法或动态规划法。,26,算法设计与分析 递归与分治总结：分治法的适用条件分治法所能,算法设计与分析 递归与分治,分治法的基本步骤:,划分：把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时也可用循环来实现。合并：把各个子问题的解合并起来。,27,算法设计与分析 递归与分治分治法的基本步骤:划分：把规模为,divide-and-conquer(P)if(|P|=n0)adhoc(P);/解决小规模的问题 divide P into smaller subinstances P1,P2,.,Pk；/分解问题 for(i=1,i=k,i+)yi=divide-and-conquer(Pi);/递归的解各子问题 return merge(y1,.,yk);/将各子问题的解合并为原问题的解,分治法的基本步骤,算法设计与分析 递归与分治,在用分治法设计算法时，最好使子问题的规模大致相同，即，将一个问题分成大小相等的k个子问题（许多问题取k=2）。使子问题规模大致相等的做法是出自一种平衡子问题的思想，这通常比子问题规模不等的做法要好。,|P|问题P的规模n0为阀值adhoc(P)基本子算法,28,divide-and-conquer(P)分治法的基本步骤算,分治法的复杂性分析,从一般设计模式看，用分治法设计的程序通常是一个递归算法。分治法将规模为n的问题分成k个规模为n/m的子问题：设n0=1,且adhoc解问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。,用T(n)（递归方程）表示该分治法求解规模为|P|=n的问题所需的计算时间：,算法设计与分析 递归与分治,29,分治法的复杂性分析从一般设计模式看，用分治法设计的程序通常是,通过迭代法求得方程解：,基本子问题花费时间,合并步花费时间,算法设计与分析 递归与分治,30,通过迭代法求得方程解：基本子问题花费时间合并步花费时间 算法,2.3 二分搜索技术,算法设计与分析 递归与分治,问题描述：已知一个按非降次序排列的元素表a1,a2,an，判定某个给定元素x是否在该表中出现，若是，则找出该元素在表中的位置，并置于j，否则，置j为0。一般解决方法：从头到尾查找一遍。,x,成功与不成功的最坏情况下需O(n)次比较,31,2.3 二分搜索技术算法设计与分析 递归与分治问题描述：已,分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件,分析：比较x和a的中间元素amid，若x=amid，则x在L中的位置就是mid；如果xai，同理我们只要在amid的后面查找x即可。无论是在前面还是后面查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。,分析：很显然此问题分解出的子问题相互独立，即在ai的前面或后面查找x是独立的子问题，因此满足分治法的适用条件。,分析：,该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。,算法设计与分析 递归与分治,32,分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以,二分搜索算法：template int BinarySearch(Type a,const Type,算法复杂度分析：每执行一次算法的while循环，待搜索数组的大小减少一半。在最坏情况下，while循环被执行O(logn)次，循环体内运算需要O(1)时间。算法在最坏情况下的计算时间复杂性为O(logn)。,算法设计与分析 递归与分治,33,二分搜索算法：算法复杂度分析：算法设计与分析 递归与分治3,2.8 快速排序,算法思路 对Ap:r,按以下步骤进行排序：(1)分解:取A中一元素为支点,将Ap:r分成3段:Ap:q-1,Aq,A q+1:r,其中A p:q-1中元素Aq,Aq+1:r中元素 Aq;(2)求解:通过递归调用分别对Ap:q-1和Aq+1:r 排序。(3)合并:合并A p:q-1,Aq,A q+1:r 为Ap:r。,算法设计与分析 递归与分治 快速排序,34,2.8 快速排序算法思路 对Ap:r,按以下步骤进行,得:Tmax(n)=O(n2),快速排序算法,template void QuickSoft(T a,int p,int r)if(pr)int q=Partition(a,p,r)QuickSort(a,p,q-1);/对左半段排序 QuickSoft(a,q+1,r);/对右半段排序,template int Partion(T a,int p,int r)int i=p;j=r+1;t x=ap；/取支点/将x的元素交换到左边/将x的元素交换到右边 while(true)while(a+i x)；if(i=j)break;swap(ai,aj);ap=aj；aj=x;return j,Tmin(n)=,O(1)n1,得:Tmin(n)=O(nlogn),复杂性分析,Tmax(n)=,O(1)n1,35,得:Tmax(n)=O(n2)快速排序算法,随机选择支点的快速排序,template void randomizedQuickSoft(T a,int p,int r)if(pr)int q=randomizedPartition(a,p,r)randomizedQuickSort(a,p,q-1);/对左半段排序 randomizedQuickSoft(a,q+1,r);/对右半段排序,算法设计与分析 递归与分治 快速排序,template int randomizedPartition(T a,int p,int r)int i=random(p,r)swap(ai,ap)return Partition(a,p,r),快速排序算法性能取决于划分的对称性,36,随机选择支点的快速排序 template cla,2.9 线性时间选择,问题陈述 求n个元素中的第k小元素.给定线性序集中n个不同的元素和一个整数k，1kn要求找出这n个元素中第k小的元素，即如果将这n个元素依其线性序排列时，排在第k个位置的元素即为我们要找的元素。当k=1时,找最小元;当k=n时,找最大元素;当k=(n+1)/2时,找中位数.,算法设计与分析 递归与分治,37,2.9 线性时间选择问题陈述 求n个元素中的第k小元,算法设计与分析 递归与分治,算法思路 模仿快速排序,对输入数组A进行二分,使子数组A1的元素 A2中的元素,分点J由随机数产生.若KJ,则K为A1的第K小元,若KJ,则K为A2的第 K-J小元.,38,算法设计与分析 递归与分治算法思路 模仿快速排序,对,算法设计与分析 递归与分治,找数组a0:n-1第k小元素调用RandomizedSelect(a,0,n-1,k),template T RandomizedSelect(a,int p,int r,int k)if(p=r)return ap;int i=RandomizedPartition(a,p,r);j=i-p+1;/支点元素是第j小个元素,左半部元素个数 if k=j return Ai;if(k j)return RandomizedSelect(a,p,i-1,k);else return RandomizedSelect(a,i+1,r,k-j);,p,r 数组范围K:第k小个元素,与快速排序算法不同,它只对子数组之一进行递归处理。,39,算法设计与分析 递归与分治找数组a0:n-1第k小元,执行RandomizedPartiton，数组ap:r划分成两个子数组ap:i和ai+1:r，其中ap:i元素ai+1:r元素计算子数组ap:i中元素个数j如果kj,则要找的第k小元素落在子数组ai+1:r中,要找的ap:r中第k小的元素是ai+1:r中的第k-j小的元素。如果k=j,找到第k小个元素，返回ai递归循环。,算法设计与分析 递归与分治,40,执行RandomizedPartiton，数组ap:r划,Tmin(n)=,d T(n)=T(n/2)+cn,分析,最坏情况:Tmax(n)=(n2)(左半总为空),(等分点),得:Tmin(n)=(n),算法设计与分析 递归与分治,41,Tmin(n)=d分析 最,最坏情况下的选择算法分析,算法设计与分析 递归与分治,算法RandomizedSelect需要(n)计算时间。例如在找最小元素时，总是在最大元素处划分。(n-1)+(n-2)+1=n算法RandomizedSelect不稳定的原因：由于随机划分函数使用了一个随机数产生器Random,产生p和r之间的一个随机整数，因此产生的划分基准是随机的。可以证明，算法可以在O(n)平均时间内找出n个输入元素中的第k小元素。,42,最坏情况下的选择算法分析算法设计与分析 递归与分治算法R,算法思路(中间的中间):将A中元素分为n/r组,除最后一组外,每组元素为r个,用任意排序算法排序,取出每组的中位数,对n/r个中位数递归调用,找到中位数,以该元素作为划分基准.,算法设计与分析 递归与分治,43,算法思路(中间的中间):算法设计与分析 递归与分治x,templateT Select(T a,int p,int r,int k)if(r-p75)用简单排序法排序；return ap+k-1；for(int i=0;i=(r-p-4)/5;i+)将ap+5*i至ap+5*i-4的第3小元素与ap+i交换位置；/找中位数的中位数 T x=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);int i=Partition(a,p,r,x),j=i-p+1;if(k=j)return Select(a,p,i,k)else return Select(a,i+1,r,k-j),最坏情况下的选择算法:,算法分析,T(n)=,得:T(n)=O(n),c1 n75c2n+T(n/5)+T(3n/4),定理:若r=5且数组中元素互不相同,则n75时,max|left|,|right|=3n/4,44,template最坏情况下的选择算法:算,2.4 大整数的乘法,问题描述设X,Y是两个n位二进制数,求X*Y.,算法设计与分析 递归与分治,一般方法：O(n2),效率太低！,分治法：,复杂性分析：,T(n)=O(n2)没有改进,45,2.4 大整数的乘法问题描述设X,Y是两个n位二进制数,分析这两个算式更复杂一些，但它们仅需要3次n/2位乘法。ac、bd和(ab)(dc),算法改进,算法设计与分析 递归与分治,为了降低时间复杂度，必须减少乘法的次数。为此，把XY写成另外的形式：,XY=ac2n+(a-b)(d-c)+ac+bd)2n/2+bd 或XY=ac2n+(a+b)(c+d)-ac-bd)2n/2+bd,结论：T(n)=O(nlog3)=O(n1.59)较大的改进,46,分析这两个算式更复杂一些，但它们仅需要3次n/2位乘法。,S=SIGN(X)*SIGN(Y)；X:=ABS(X)；Y:=ABS(Y)；if n=l then if(X=1)and(Y=1)then return(S)else return(0)else A:=X的左边n/2位；B:=X的右边n/2位；C:=Y的左边n/2位；D:=Y的右边n/2位；m1:=MULT(A，C，n/2)；m2:=MULT(A-B,D-C，n/2)；m3:=MULT(B，D，n/2)；S:=S*(m1*2n+(m1+m2+m3)*2n/2+m3)；return(S),X,Y为2个小于2n的二进制整数，S=XY,function MULT(X,Y,n),大数相乘的分治递归算法,二进制大整数乘法同样可应用于十进制大整数的乘法.,存放XY的符号,存放三个乘积,算法,47,S=SIGN(X)*SIGN(Y)；X,Y为2个小于2,2.5 Strassen矩阵相乘法,常规算法设矩阵A=(aij)nn,B=(bij)nn,C=AB=(cij)nn,计算C共需nn2个乘法,n2(n-1)个加法.,T(n)=O(n3),算法设计与分析 递归与分治,如果依此定义来计算矩阵A和B的乘积矩阵C，则每计算C的一个元素Ci,j，需要做n次乘法和n-1次加法。,48,2.5 Strassen矩阵相乘法常规算法设矩阵A=(a,算法设计与分析 递归与分治,C11=A11B11+A12B21 C12=A11B12+A12B22C21=A21B11+A22B21 C22=A21B12+A22B22,首先假定n是2（n=2k）的幂，如果相乘的两矩阵A和B不是方阵，可以通过适当添加全零行和全零列，使之成为行列数为2的幂的方阵。使用分治法，将矩阵A、B和C中每一矩阵都分块成4个大小相等的子矩阵，每个子矩阵都是n/2n/2的方阵。由此可将方程C=AB重写为：,算法思路,49,算法设计与分析 递归与分治C11=A11B11+A12B,算法设计与分析 递归与分治,如果n=2，则两个2阶方阵的乘积可以直接计算出来，共需8次乘法和4次加法。当子矩阵的阶大于2时，可以继续将子矩阵分块，直到子矩阵的阶降为2。这样，就产生了一个分治降阶的递归算法。依此算法，计算2个n阶方阵的乘积转化为计算8个n/2阶方阵的乘积和4个n/2阶方阵的加法。2个n/2n/2矩阵的加法显然可以在c*n2/4(O(n2)时间内完成，这里c是一个常数。上述分治法的计算时间耗费T(n)的递归方程满足：,T(n)=O(n3),没有改进，原因是没有减少矩阵乘法次数。,50,算法设计与分析 递归与分治如果n=2，则两个2阶方阵的乘,算法设计与分析 递归与分治,为了降低时间复杂度，必须减少乘法次数，其关键在于计算2个2阶方阵的乘积时所用乘法次数能否少于8次。为此，Strassen提出了一种只用7次乘法运算计算2阶方阵乘积的方法（但增加了加/减法次数）：M1=A11(B12-B22)，M2=(A11+A12)B22 M3=(A21+A22)B11，M4=A22(B21-B11)M5=(A11+A22)(B11+B22)，M6=(A12-A22)(B21+B22)M7=(A11-A21)(B11+B12),51,算法设计与分析 递归与分治为了降低时间复杂度，必须减少乘,C11=M5+M4-M2+M6C12=M1+M2C21=M3+M4C22=M5+M1-M3-M7,算法设计与分析 递归与分治,得:T(n)=O(nlog7)=O(n2.81),分析,做了这7次乘法后，再做若干次加/减法就可以得到：,较大的改进,52,C11=M5+M4-M2+M6算法设计与分析 递,procedure STRASSEN(n,A,B,C)；if n=2 then MATRIX_MULTIPLY(A,B,C)else 将矩阵A和B分块；STRASSEN(n/2，A11，B12-B22，M1)；STRASSEN(h/2，A11+A12，B22，M2)；STRASSEN(n/2，A21+A22，B11，M3)；STRASSEN(n/2，A22，B21-B11，M4)；STRASSEN(n/2，A11+A22，B11+B22，M5)STRASSEN(n/2，A12-A22，B21+B22，M6)；STRASSEN(n/2，A11+A21，B11+B12，M7),C:=,矩阵相乘 Strassen 算法,算法,算法设计与分析 递归与分治,53,procedure STRASSEN(n,A,B,C),问题陈述在一个2k 2k个方格组成的棋盘中,恰有一方格残缺,残缺方格的位置有22k种。故对任何k0,残缺棋盘有22k种.要求用L型骨牌覆盖残缺棋盘上的所有方格且任何2个L型骨牌不得重叠覆盖。,2.6 棋盘覆盖,算法设计与分析 递归与分治,54,问题陈述在一个2k 2k个方格组成的棋盘中,恰有一方格,2k 2k 的棋盘覆盖中，用到的骨牌数为(4k-1)/3,算法设计与分析 递归与分治,55,2k 2k 的棋盘覆盖中，用到的骨牌数为(4k-1)/3算,算法思路 当k0时,将2k 2k棋盘分割为4个2k-1 2k-1子棋盘,残缺方格必位于4个子棋盘之一.其余3个子棋盘中无残缺方格.,用一个L型骨牌覆盖这3个较小棋盘的结合处.这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的残缺方格,原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为1 1棋盘.,算法设计与分析 递归与分治,为此将剩余3棋盘转化为残缺棋盘:,56,算法思路 当k0时,将2k 2k棋盘分割为4个2k-,算法分析 设T(k)为覆盖2k 2k残缺棋盘的时间,当k=0时覆盖它需要常数时间O(1).当k0时,测试哪个子棋盘残缺以及形成3个残缺子棋盘需要O(1),覆盖4个残缺子棋盘需四次递归调用,共需时间4T(k-1).,T(k)=,O(1)4T(k-1)+O(1),迭代法解得:T(k)=(4k),与所需骨牌数同阶,算法设计与分析 递归与分治,57,算法分析 设T(k)为覆盖2k 2k残缺棋盘的时间,void ChessBoard(int tr,int tc,int dr,int dc,int size)if(size=1)return；int t=tile+，/L型骨牌数 s=size2；/分割棋盘/覆盖左上角子棋盘 if(dr tr+s&dc tc+S)/特殊方格在此棋盘中 ChessBoard(tr,tc,dr,dc,S)；else/此棋盘中无特殊方格/用t号L型骨牌覆盖右下角 Boardtr+s-1tc+s-1=t；/覆盖其余方格 Chessboard(tr，tc，tr+s-1，tc+s-l，s)；,算法设计与分析 递归与分治,tr:左上角方格行tc:左上角方格列dr:残缺方格行dc:残缺方格列size:棋盘行数Board:为全局变量二维数组表示棋盘,58,void ChessBoard(int tr,int tc,/覆盖右上角子棋盘 if(dr=tc+S)/特殊方格在此棋盘中 ChessBoard(tr，tc+s，dr，dc，S)；else/此棋盘中无特殊方格/用t号骨牌覆盖左下角 Boardtr+s-1tc+s=t；/覆盖其余方格 Chessboard(tr，tc+s，tr+s-1，tc+s，s)；.,void outputBoard(int size)for int i=0;isize;i+)for int j=0;jsize;j+)；coutsetw(5)board ij;coutendl;,算法设计与分析 递归与分治,59,/覆盖右上角子棋盘void outputBoard(,算法设计与分析 递归与分治,给定平面S上n个点,找其中的一对点,使得在 n(n-1)/2 个点对中,该点对的距离最小。,2.10 最接近点对问题,问题描述,简化问题（一维问题）为了使问题易于理解和分析，先来考虑一维的情形。此时，S中的n个点退化为x轴上的n个实数 x1,x2,xn。最接近点对即为这n个实数中相差最小的2个实数。,60,算法设计与分析 递归与分治,算法设计与分析 递归与分治,假设我们用x轴上某个点m将S划分为2个子集S1和S2，基于平衡子问题的思想，用S中各点坐标的中位数来作分割点。递归地在S1和S2上找出其最接近点对p1,p2和q1,q2，并设d=min|p1-p2|,|q1-q2|，S中的最接近点对或者是p1,p2，或者是q1,q2，或者是某个p3,q3，其中p3S1且q3S2。能否在线性时间内找到p3,q3？,61,算法设计与分析 递归与分治假设我们用x轴上某个点m将S划,算法设计与分析 递归与分治,如果S的最接近点对是p3,q3，即|p3-q3|d，则p3和q3两者与m的距离不超过d，即p3(m-d,m，q3(m,m+d。由于在S1中，每个长度为d的半闭区间至多包含一个点（否则必有两点距离小于d），并且m是S1和S2的分割点，因此(m-d,m中至多包含S中的一个点。由图可以看出，如果(m-d,m中有S中的点，则此点就是S1中最大点。同理,如果(m,m+d中有S中的点，则此点就是S2中最小点。用线性时间就能找到区间(m-d,m和(m,m+d中所有点，即p3和q3。用线性时间就可以将S1的解和S2的解合并成为S的解。,能否在线性时间内找到p3,q3？,62,算法设计与分析 递归与分治如果S的最接近点对是p3,q,算法设计与分析 递归与分治,Bool Cpairl(S,d)n=|S|;if(n2)d=MAX;return false;m=S中各点坐标的中位数;Cpairl(S1,d1);/找到S1中最短距离 Cpairl(S2,d2);/找到S2中最短距离 p=max(S1);q=min(S2);/找到S1和S2中相邻接点 d=min(d1,d2,q-p);return true;,T(n)=,O(1)T(n)=2T(n/2)+O(n),得:T(n)=O(nlogn),63,算法设计与分析 递归与分治Bool Cpairl(S,d,1)n较小时直接求(n=2).2)将S上的n个点分成大致相等的2个子集S1和S2 3)分别求S1和S2中的最接近点对 4)求一点在S1、另一点在S2中的最近点对 5)从上述三对点中找距离最近的一对.,算法设计与分析 递归与分治,算法思路,二维平面的情况：,64,1)n较小时直接求(n=2).,p1,p2,l,算法设计与分析 递归与分治,设 d1,d2分别为s1,s2中最近点对的距离,d=mind1,d2,设p1,p2分别为分割线l左右宽为d的垂直长条区域,若第三个最近点对d 必在p1和p2中。对pp1,检查p2中 满足p.y-dq.yp.y+d 的点q,判断是否q与p的距离小于d?,65,p1p2l算法设计与分析 递归,算法设计与分析 递归与分治,考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有distance(p，q)d。满足这个条件的P2中的点一定落在一个d2d的矩形R中由d的意义可知，P2中任何2个S中的点的距离都不小于d。由此可以推出矩形R中最多只有6个S中的点。因此，在分治法的合并步骤中最多只需要检查6n/2=3n个候选者,p,2d,2d,p的比较区,最多含6个点,66,算法设计与分析 递归与分治考虑P1中任意一点p，它若与P,证明:将矩形R的长为2d的边3等分，将它的长为d的边2等分，由此导出6个(d/2)(2d/3)的矩形。若矩形R中有多于6个S中的点，则由鸽舍原理易知至少有一个(d/2)(2d/3)的小矩形中有2个以上S中的点。设u，v是位于同一小矩形中的2个点，则distance(u,v)5d/6d。这与d的意义相矛盾。,算法设计与分析 递归与分治,67,证明:将矩形R的长为2d的边3等分，将它的长为d的边2等分，,算法设计与分析 递归与分治,为了确切地知道要检查哪6个点，可以将p和P2中所有S2的点投影到垂直线l上。由于能与p点一起构成最接近点对候选者的S2中点一定在矩形R中，所以它们在直线l上的投影点距p在l上投影点的距离小于d。由上面的分析可知，投影点最多只有6个。将P1和P2中所有S中点按其y坐标排好序，则对P1中所有点，对排好序的点列作一次扫描可找出所有最接近点对的候选者。对P1中每一点最多只要检查P2中排好序的相继6个点。,68,算法设计与分析 递归与分治为了确切地知道要检查哪6个点，,public static