1、第一章第一章 算法概述算法概述第二章第二章 递归与分治策略递归与分治策略第三章第三章 动态规划动态规划第四章第四章 贪心算法贪心算法第五章第五章 回朔法回朔法第六章第六章 分支限界法分支限界法第七章第七章 概率算法概率算法算法设计与分析算法设计与分析 目录目录算法设计与分析算法设计与分析 递归与分治递归与分治2.1 直接或间接地调用自身的算法称为递归算递归算法法。由分治法产生的子问题往往是原问题的较小模式，为使用递归技术提供了方便。反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解，自然导致递归过程的产生。算法设计与分析算法设计与分析 递归与
2、分治递归与分治当子问题足够大当子问题足够大,需要递归求解时需要递归求解时,称为称为递递归情况归情况;当子问题足够小时当子问题足够小时,不再需要递归时不再需要递归时,递归递归进入进入“触底触底”,进入进入基本情况基本情况;用函数自身给出定义的函数称为用函数自身给出定义的函数称为递归函递归函数数;递归式递归式是一个等式或不等式是一个等式或不等式,它通过更小它通过更小的输入上的函数值来描述一个函数的输入上的函数值来描述一个函数.递归函数的内部执行过程 l（1）运行开始时，为递归调用建立一个）运行开始时，为递归调用建立一个工作栈工作栈，其结构包括实参、局部变量和返回地址；其结构包括实参、局部变量和返回
3、地址；l（2）每次执行递归调用之前，把递归函数的实）每次执行递归调用之前，把递归函数的实参和局部变量的当前值以及调用后的返回地址参和局部变量的当前值以及调用后的返回地址压栈压栈；l（3）每次递归调用结束后，将栈顶元素）每次递归调用结束后，将栈顶元素出栈出栈，使相应的实参和局部变量恢复为调用前的值，使相应的实参和局部变量恢复为调用前的值，然后转向返回地址指定的然后转向返回地址指定的位置继续执行位置继续执行算法设计与分析算法设计与分析 递归与分治递归与分治算法设计与分析算法设计与分析 递归与分治递归与分治例例2-3 2-3 Ackerman函数函数当一个函数及它的一个变量是由函数自身定义时，称这个
4、函数是双递归函数双递归函数。Ackerman函数A(n，m)定义如下：1,20)1),1(),(2)0,(1),0(2)0,1(mnnmmmnAAmnAnnAmAA该变量是由函数自身定义分析分析:A(n,m)的自变量m的每一个值都定义了一个单变量函数：M=0时时，A(n,0)=n+2 M=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
5、=3时，类似的可以推出 M=4时，A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数。n2222算法设计与分析算法设计与分析 递归与分治递归与分治算法设计与分析算法设计与分析 递归与分治递归与分治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)=22、证明、证明A(n,1)=2n (n=1)因为因为n,m=1 使用递归式使用递归式(4)得得A(n,1)=A(A(n-1,1),0)由公式由公式(3
6、)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算法设计与分析算法设计与分析 递归与分治递归与分治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)可以看出随着可以看出随着
7、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公式得证公式得证 定义单变量的Ackerman函数A(n)为：A(n)=A(n,n)。定义其拟逆函数(n)为：(n)=minkA(k)n。即(n)是使nA(k)成立的最小的k值。(n)在复杂度分析中常遇到。对于通常所见到的正整数n，有(n)4。但在
8、理论上(n)没有上界，随着n的增加，它以难以想象的慢速度趋慢速度趋向正无穷大。向正无穷大。算法设计与分析算法设计与分析 递归与分治递归与分治递归树 T(n)=3T(n/4)+O(n 2)算法设计与分析算法设计与分析 递归与分治递归与分治算法设计与分析算法设计与分析 递归与分治递归与分治补充：主方法（定理）求解这类递推式的方法是主方法，主方法依赖于下面的主定理，使用主定理可直接得到递推式的解。定理（主定理）：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)
9、=O(nlogba-)，则T(n)=(nlogba)；（2）若f(n)=(nlogba)，则T(n)=(nlogbalogn)；（3）若对于某常数0，有f(n)=(nlogba+)，且对于某个常数c 递归与分治递归与分治 定理（主定理）：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)+nT(n)=aT(n/b)+f(n)算法设计与分析算法设计与分析 递归与分治递归
10、与分治 定理（主定理）：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)+1T(n)=aT(n/b)+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)=(nlogb
11、a+)，且对于某个常数c 递归与分治递归与分治优点：优点：结构清晰，可读性强，而且容易结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方此它为设计算法、调试程序带来很大方便。便。缺点：缺点：递归算法的运行效率较低，无论递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间是耗费的计算时间还是占用的存储空间都比非递归算法要多。都比非递归算法要多。算法设计与分析算法设计与分析 递归与分治递归与分治解决方法：解决方法：在递归算法中消除递归调用，使其转在递归算法中消除递归调用，使其转化为非递归算法。化为非递归算法。
12、1 1、采用一个用户定义的栈来模拟系统的递归调、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效只不过人工做了本来由编译器做的事情，优化效果不明显。果不明显。2 2、用递推来实现递归函数。、用递推来实现递归函数。3 3、通过、通过变换能变换能将一些递归转化为尾递归，从而将一些递归转化为尾递归，从而迭代求出结果。迭代求出结果。后两种方法在时空复杂度上均有较大改善，后两种方法在时空复杂度上均有较大改善，但其适用范围有限。但其适用范围有限。算法设计与分析算法设计与分析 递归与分治递
13、归与分治尾递归是尾递归是在递归调用时“积累”之前调用的结果，并将其传入下一次递归调用中,将递归方法中的需要的“所有状态”通过方法的参数传入下一次调用中.算法设计与分析算法设计与分析 递归与分治递归与分治尾递归只会占用恒量的内存,形式上只要最后一个return语句是单纯函数就可以2.2分治法的基本思想算法设计与分析算法设计与分析 递归与分治递归与分治将一个规模为将一个规模为n的问题的问题分解分解为为k个规模较小的子个规模较小的子问题，这些子问题问题，这些子问题互相独立互相独立且与且与原问题相同原问题相同。对这对这k个子问题分别求解个子问题分别求解。如果子问题的规模仍。如果子问题的规模仍然不够小，
14、则再划分为然不够小，则再划分为k个子问题，如此递归的个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其进行下去，直到问题规模足够小，很容易求出其解为止。解为止。将求出的小规模的问题的解将求出的小规模的问题的解合并合并为一个更大规为一个更大规模的问题的解，模的问题的解，自底向上自底向上逐步求出原来问题的解。逐步求出原来问题的解。子问题子问题1的规模是的规模是n/2 子问题子问题1的解的解 子问题子问题2的解的解 子问题子问题2的规模是的规模是n/2 原问题的解原问题的解 原问题原问题的规模是的规模是n算法设计与分析算法设计与分析 递归与分治递归与分治算法设计与分析算法设计与分析 递归
15、与分治递归与分治问题（问题（N个输入）个输入）子问题子问题1子问题子问题2子问题子问题K子问题子问题1子问题子问题2子问题子问题k相同类型相同类型合并解合并解 分治法要求分解成分治法要求分解成同类子问题同类子问题，并允许不断，并允许不断分解，使问题规模逐步减小，最终分解，使问题规模逐步减小，最终可用已知可用已知的方法求解的方法求解足够小的问题。足够小的问题。算法设计与分析算法设计与分析 递归与分治递归与分治举例举例：二路归并排序二路归并排序分解过程：分解过程：对任意长度为对任意长度为n的序列排序，首先将问的序列排序，首先将问题不断分解，直至问题可直接求解。题不断分解，直至问题可直接求解。长度为
16、长度为n的序列分解为的序列分解为2个个n/2的子序列，依次循环，直的子序列，依次循环，直至分解为至分解为n个长度为个长度为1的序列，显然长度为的序列，显然长度为1的序列是的序列是有有序表序表。合并过程：合并过程：将已排序的的子序列不断合并，形成将已排序的的子序列不断合并，形成长度为长度为n的排序序列。的排序序列。然后反复进行两两归并为然后反复进行两两归并为n/2个有序表；再对个有序表；再对n/2个有序个有序表两两归并，循环直到得到长度为表两两归并，循环直到得到长度为n的有序线性表。的有序线性表。算法设计与分析算法设计与分析 递归与分治递归与分治template void MergeSort(T
17、ype 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问题分解：规模为问题分解：规模为原来的一半；问题原来的一半；问题性质不变。性质不变。template vo
18、id MergeSort(Type a,int left,int right)if(left 递归与分治递归与分治时间复杂度时间复杂度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&lb=n)if(claclb)dlc+=cla+;else dlc+=clb+;while(la=m)dlc+=cla+;while(lb 递归与分治递归与分治算法设计与分析算法设计与分析 递归与分治递归与分治总结总结：分治法的适用条件分治法的适用
19、条件分治法所能解决的问题一般具有以下特征：分治法所能解决的问题一般具有以下特征：1.1.该问题规模缩小到一定的程度就可以容易地该问题规模缩小到一定的程度就可以容易地解决；解决；2.2.该问题可以分解为若干个规模较小的相同子该问题可以分解为若干个规模较小的相同子问题，即该问题具有问题，即该问题具有最优子结构性质最优子结构性质；3.3.利用该问题分解出的子问题的解可以合并为利用该问题分解出的子问题的解可以合并为该问题的解；该问题的解；4.4.该问题所分解出的各个子问题是该问题所分解出的各个子问题是相互独立相互独立的，的，即子问题之间不包含公共的子问题。即子问题之间不包含公共的子问题。应用分治法的前
20、提，它应用分治法的前提，它也是大多数问题可以满也是大多数问题可以满足的，此特征反映了足的，此特征反映了递递归思想归思想的应用。的应用。关键特征关键特征，能否利用分治法完，能否利用分治法完全取决于问题是否具有第四条全取决于问题是否具有第四条特征，如果具备了第一条和第特征，如果具备了第一条和第二条特征，而不具备第四条特二条特征，而不具备第四条特征，则可以考虑征，则可以考虑贪心法贪心法或或动态动态规划法规划法。算法设计与分析算法设计与分析 递归与分治递归与分治分治法的基本步骤分治法的基本步骤:1.划分：划分：把规模为把规模为n的原问题划分为的原问题划分为k个规个规模较小的子问题，并尽量使这模较小的子
21、问题，并尽量使这k个子问题个子问题的规模大致相同。的规模大致相同。2.求解子问题：求解子问题：各子问题的解法与原问题各子问题的解法与原问题的解法通常是相同的，可以用的解法通常是相同的，可以用递归递归的方的方法求解各个子问题，有时也可用循环来法求解各个子问题，有时也可用循环来实现。实现。3.合并：合并：把各个子问题的解合并起来。把各个子问题的解合并起来。divide-and-conquer(P)if(|P|=n0)adhoc(P);/解决小规模的问题 divide P into smaller subinstances P1,P2,.,Pk；/分解问题 for(i=1,i 递归与分治递归与分治
22、在用分治法设计算法时，最好使子问题的规模大致相同，在用分治法设计算法时，最好使子问题的规模大致相同，即，将一个问题即，将一个问题分成大小相等的分成大小相等的k个子问题个子问题（许多问题取（许多问题取k=2）。）。使子问题规模大致相等的做法是出自一种使子问题规模大致相等的做法是出自一种平衡子问题平衡子问题的的思想，这通常比子问题规模不等的做法要好。思想，这通常比子问题规模不等的做法要好。|P|问题问题P的规模的规模n0为阀值为阀值adhoc(P)基本子算法基本子算法分治法的复杂性分析 从一般设计模式看，用分治法设计的程序通常是一个递归算法。分治法将规模为n的问题分成k k个规模为个规模为n/mn
23、/m的子问题的子问题：设n0=1,且adhoc解问题耗费1 1个单位时间个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间个单位时间。用用T(n)（递归方程）表示（递归方程）表示该分治法求解规模为该分治法求解规模为|P|=n的问题所需的计算时间：的问题所需的计算时间：11)()/()1()(nnnfmnkTOnT算法设计与分析算法设计与分析 递归与分治递归与分治11)()/()1()(nnnfmnkTOnT通过迭代法求得方程解：通过迭代法求得方程解：1log0log)/()(nmjjjkmmnfknnT基本子问题基本子问题花费时间花费
24、时间合并步花费合并步花费时间时间 算法设计与分析算法设计与分析 递归与分治递归与分治2.3 二分搜索技术算法设计与分析算法设计与分析 递归与分治递归与分治 问题描述：问题描述：已知一个按非降次序排列的元素表a1,a2,an，判定某个给定元素x是否在该表中出现，若是，则找出该元素在表中的位置，并置于j，否则，置j为0。一般解决方法：一般解决方法：从头到尾查找一遍。a1a2a3a4anx成功与不成功的最坏情况下需成功与不成功的最坏情况下需O(n)次比较次比较分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件分析：比较x和a的中间元素
25、amid，若x=amid，则x在L中的位置就是mid；如果xai，同理我们只要在amid的后面查找x即可。无论是在前面还是后面查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。分析：很显然此问题分解出的子问题相互独立，即在ai的前面或后面查找x是独立的子问题，因此满足分治法的适用条件。分析：分析：该问题的规模缩小到一定的程度就可以容易地该问题的规模缩小到一定的程度就可以容易地解决；解决；该问题可以分解为若干个规模较小的相同问题该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的子问题的解可以合
26、并为原问题的解；分解出的各个子问题是相互独立的。分解出的各个子问题是相互独立的。算法设计与分析算法设计与分析 递归与分治递归与分治二分搜索算法二分搜索算法：template int BinarySearch(Type a,const Type&x,int l,int r)while(r=l)int m=(l+r)/2;if(x=am)return m;if(x 递归与分治递归与分治2.8 快速排序算法思路 对Ap:r,按以下步骤进行排序按以下步骤进行排序：(1)分解分解:取取A中一元素为支点中一元素为支点,将将Ap:r分成分成3段段:Ap:q-1,Aq,A q+1:r,其中其中l A p:q-
27、1中元素中元素 Aq,l Aq+1:r中元素中元素 Aq;(2)求解求解:通过递归调用分别对通过递归调用分别对Ap:q-1和和Aq+1:r 排排序。序。(3)合并合并:合并合并A p:q-1,Aq,A q+1:r 为为Ap:r。算法设计与分析算法设计与分析 递归与分治递归与分治 快速排序快速排序 得得:T:Tmaxmax(n)=O(n(n)=O(n2 2)快速排序算法快速排序算法 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
28、+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 T Tminmin(n)=(n)=O(1)n=1O(1)n12T(n/2)+O(n)n1 得得:T:Tminmin(n)=O(nlogn)(n)=O(nlogn)复杂性分析 T Tmaxmax(n)=(n)=O(1)n=1O(1)n1T(n-1)+O(n)n1
29、随机选择支点的快速排序 template void randomizedQuickSoft(T a,int p,int r)if(p 递归与分治递归与分治 快速排序快速排序 template int randomizedPartition(T a,int p,int r)int i=random(p,r)swap(ai,ap)return Partition(a,p,r)快速排序算法性能取决于划分的对称性2.9 线性时间选择线性时间选择问题陈述 求求n个元素中的第个元素中的第k小元素小元素.给定线性序集中n个不同的元素和一个整数k，1 k n要求找出这n个元素中第k小的元素，即如果将这n个元素
30、依其线性序排列时，排在第k个位置的元素即为我们要找的元素。当当k=1时时,找最小元找最小元;当当k=n时时,找最大元素找最大元素;当当k=(n+1)/2时时,找中位数找中位数.算法设计与分析算法设计与分析 递归与分治递归与分治算法设计与分析算法设计与分析 递归与分治递归与分治算法思路 模仿快速排序模仿快速排序,对输入数组对输入数组A进行二分进行二分,使使子数组子数组A1的元素的元素 A2中的元素中的元素,分点分点J由随机数产生由随机数产生.若若K J,则则K为为A1的第的第K小元小元,若若KJ,则则K为为A2的第的第 K-J小元小元.算法设计与分析算法设计与分析 递归与分治递归与分治找数组a0
31、: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小个元素与
32、快速排序与快速排序算法不同算法不同,它它只对子数组只对子数组之一进行递之一进行递归处理。归处理。执行执行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递归循环。递归循环。算法设计与分析算
33、法设计与分析 递归与分治递归与分治 T Tminmin(n)=(n)=d d T(n)=T(n/2)+cn T(n)=T(n/2)+cn 分析分析 最坏情况最坏情况:T:Tmaxmax(n)=(n)=(n2)(左半总为空左半总为空)(等分点等分点)得得:T:Tminmin(n)=(n)=(n)(n)算法设计与分析算法设计与分析 递归与分治递归与分治最坏情况下的选择算法分析最坏情况下的选择算法分析算法设计与分析算法设计与分析 递归与分治递归与分治算法算法RandomizedSelectRandomizedSelect需要需要(n)(n)计算时间。计算时间。例如在找最小元素时，总是在最大元素处划分
34、。例如在找最小元素时，总是在最大元素处划分。(n-1)+(n-2)+1=n(n-1)+(n-2)+1=n算法算法RandomizedSelectRandomizedSelect不稳定的原因：不稳定的原因：由于随机划分函数使用了一个随机数产生器由于随机划分函数使用了一个随机数产生器Random,Random,产生产生p p和和r r之间的一个随机整数，因此之间的一个随机整数，因此产生的划分基准是随机的。产生的划分基准是随机的。可以证明，算法可以在可以证明，算法可以在O(n)O(n)平均时间内找平均时间内找出出n n个输入元素中的第个输入元素中的第k k小元素。小元素。算法思路(中间的中间):将将
35、A中元素分为中元素分为n/r组组,除最后一组外除最后一组外,每组元素为每组元素为r个个,用任意排序算法排序用任意排序算法排序,取出每组的中位数取出每组的中位数,对对n/r个中位数递归调用个中位数递归调用,找到中位数找到中位数,以该元素作为划分基准以该元素作为划分基准.算法设计与分析算法设计与分析 递归与分治递归与分治xtemplateT 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交换位置；/找中位数的中位数
36、 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)=得得:T(n)=O(n):T(n)=O(n)c c1 1 n75n75时时,max|left|,|right|递归与分治递归与分治 一般方法：一般方法：O(n2)效率太低！效率太低！分治法：分治法：bdbcadacXYdcYbaXnnnn 2222)(222 复杂性分析：复杂性分析
37、：12/411nnOnTnOnT n/2n/2位位 n/2n/2位位 n/2n/2位位 n/2n/2位位X=X=Y=Y=ABCDT(n)=O(n2)没有改进没有改进分析分析这两个算式更复杂一些，但它们仅需要这两个算式更复杂一些，但它们仅需要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 12/311nnOnTnOnT结论：结
38、论：T(n)=O(nlog3)=O(n1.59)较大的改进较大的改进 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,YX,Y为为2 2个小于个小于2 2
39、n n的二进制整数，的二进制整数，S=XYS=XYfunction MULT(X,Y,n)大数相乘的分治递归算法大数相乘的分治递归算法二进制大整数二进制大整数乘法同样可应乘法同样可应用于十进制大用于十进制大整数的乘法整数的乘法.存放存放XY的符号的符号存放三个乘积存放三个乘积算法算法2.5 Strassen矩阵相乘法矩阵相乘法常规算法 设矩阵设矩阵A=(aij)n n,B=(bij)n n,C=A B=(cij)n n 计算C共需nn2个乘法,n2(n-1)个加法.T(n)=O(nT(n)=O(n3 3)算法设计与分析算法设计与分析 递归与分治递归与分治 nkkjikijbac1 如果依此定义
40、来计算矩阵如果依此定义来计算矩阵A和和B的乘积矩阵的乘积矩阵C，则，则每计算每计算C的一个元素的一个元素Ci,j，需要做，需要做n次乘法和次乘法和n-1次次加法。加法。算法设计与分析算法设计与分析 递归与分治递归与分治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的方阵。由此可将方程
41、C=AB重写为：222112112221121122211211BBBBAAAACCCC算法思路 算法设计与分析算法设计与分析 递归与分治递归与分治 如果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)的递归方程满足：22/8212nnOnTn
42、OnTT(n)=O(n3)没有改进，原因是没有减少矩阵乘法没有改进，原因是没有减少矩阵乘法次数。次数。算法设计与分析算法设计与分析 递归与分治递归与分治为了降低时间复杂度，必须减少乘法次数，其关键在于计为了降低时间复杂度，必须减少乘法次数，其关键在于计算算2个个2阶方阵的乘积时所用乘法次数能否少于阶方阵的乘积时所用乘法次数能否少于8次。为此，次。为此，Strassen提出了一种只用提出了一种只用7次乘法运算次乘法运算计算计算2阶方阵乘积的方法阶方阵乘积的方法（但增加了加（但增加了加/减法次数）：减法次数）：M1=A11(B12-B22)，M2=(A11+A12)B22 M3=(A21+A22)
43、B11，M4=A22(B21-B11)M5=(A11+A22)(B11+B22)，M6=(A12-A22)(B21+B22)M7=(A11-A21)(B11+B12)731543216245MMMMMMMMMMMMC11=M5+M4-M2+M6C12=M1+M2C21=M3+M4C22=M5+M1-M3-M7算法设计与分析算法设计与分析 递归与分治递归与分治 得得:T(n)=O(n:T(n)=O(nlog7log7)=O(n =O(n2.812.81)分析 做了这做了这7次乘法后，再做若干次加次乘法后，再做若干次加/减法就可以得到：减法就可以得到：22/7212nnOnTnOnT 较大的改进较
44、大的改进procedure STRASSEN(n,A,B,C)；if n=2 then MATRIX_MULTIPLY(A,B,C)else 将矩阵将矩阵A A和和B 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
45、，M7)731543216245MMMMMMMMMMMMC:=矩阵相乘矩阵相乘 Strassen 算法算法算法算法算法设计与分析算法设计与分析 递归与分治递归与分治问题陈述在一个在一个2k 2k个方格组成的棋盘中个方格组成的棋盘中,恰有一方恰有一方格残缺格残缺,残缺方格的位置有残缺方格的位置有22k种。故对任何种。故对任何k0,残缺棋残缺棋盘有盘有22k种种.要求用要求用L型骨牌覆盖残缺棋盘上的所有方格型骨牌覆盖残缺棋盘上的所有方格且任何且任何2个个L型骨牌不得重叠覆盖。型骨牌不得重叠覆盖。2.6 6 棋盘覆盖棋盘覆盖算法设计与分析算法设计与分析 递归与分治递归与分治2k 2k 的棋盘覆盖中，
46、用到的骨牌数为的棋盘覆盖中，用到的骨牌数为(4k-1)/3算法设计与分析算法设计与分析 递归与分治递归与分治 算法思路 当当k0时时,将将2k 2k棋盘分割为棋盘分割为4个个2k-1 2k-1子子棋盘棋盘,残缺方格必位于残缺方格必位于4个子棋盘之一个子棋盘之一.其余其余3个子棋盘中个子棋盘中无残缺方格无残缺方格.用一个用一个L型骨牌覆盖这型骨牌覆盖这3个较小棋盘的结合处个较小棋盘的结合处.这这3个个子棋盘上被子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的残缺型骨牌覆盖的方格就成为该棋盘上的残缺方格方格,原问题转化为原问题转化为4个较小规模的棋盘覆盖问题。递归个较小规模的棋盘覆盖问题。递归地使用这
47、种分割，直至棋盘简化为地使用这种分割，直至棋盘简化为1 1棋盘棋盘.算法设计与分析算法设计与分析 递归与分治递归与分治为此将剩余为此将剩余3棋盘转化为残缺棋盘棋盘转化为残缺棋盘:算法分析 设设T(k)T(k)为为覆盖覆盖2k 2k残缺棋盘残缺棋盘的时间的时间,当当k=0时覆盖它需要常数时间时覆盖它需要常数时间O(1).当当k0时时,测试哪个子棋盘残缺以及形成测试哪个子棋盘残缺以及形成3个残缺子个残缺子棋盘需要棋盘需要O(1),覆盖覆盖4个残缺子棋盘需四次递归调用个残缺子棋盘需四次递归调用,共需时间共需时间4T(k-1)T(k-1).T(k)=T(k)=O(1)4T(k-1)+4T(k-1)+O
48、(1)迭代法解得迭代法解得:T(k)=:T(k)=(4(4k k)与所需骨与所需骨牌数同阶牌数同阶算法设计与分析算法设计与分析 递归与分治递归与分治void ChessBoard(int tr,int tc,int dr,int dc,int size)void ChessBoard(int tr,int tc,int dr,int dc,int size)if(size=1)return if(size=1)return；int t=tile+int t=tile+，/L L型骨牌数型骨牌数 s=sizes=size2 2；/分割棋盘分割棋盘 /覆盖左上角子棋盘覆盖左上角子棋盘 if(dr
49、tr+s&dc tc+S)if(dr tr+s&dc 递归与分治递归与分治tr:左上角方格行左上角方格行tc:左上角方格列左上角方格列dr:残缺方格行残缺方格行dc:残缺方格列残缺方格列size:棋盘行数棋盘行数Board:为全局变量为全局变量二维数组表示棋盘二维数组表示棋盘 /覆盖右上角子棋盘覆盖右上角子棋盘 if(dr=tc+S)/特殊方格在此棋盘中特殊方格在此棋盘中 ChessBoard(tr，tc+s，dr，dc，S)；else/此棋盘中无特殊方格此棋盘中无特殊方格 /用用t t号骨牌覆盖左下角号骨牌覆盖左下角 Boardtr+s-1tc+s=t；/覆盖其余方格覆盖其余方格 Chess
50、board(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;cout 递归与分治递归与分治算法设计与分析算法设计与分析 递归与分治递归与分治 给定平面给定平面S上上n个点个点,找其中的一对点找其中的一对点,使得在使得在 n(n-1)/2 个点对中个点对中,该点对的距离最小。该点对的距离最小。2.10 最接近点对问题问题描述u简化问题（一维问题）u为了使问题易于理解和分析，先来考虑一一维的情形。此时，S中的n个点退化为x
