《算法设计与分析Chapter2Veron》由会员分享，可在线阅读，更多相关《算法设计与分析Chapter2Veron（73页珍藏版）》请在金锄头文库上搜索。
1、1,递归与分治策略,张可佳,2,理解递归的概念 掌握设计有效算法的分治策略 通过下面的范例学习分治策略设计技巧 二分搜索技术； 大整数乘法； Strassen矩阵乘法； 合并排序和快速排序； 线性时间选择； 最接近点对问题；,学习要点,3,递归的概念,递归,递归的概念 直接或间接调用自身的算法称为递归算法 用函数自身给出定义的函数称为递归函数,4,递归函数（阶乘函数）,阶乘函数,5,边界条件,递归方程,边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。,int fractorial (int n) If(n=0) return 1; return
2、 n*fractorial(n-1); ,递归函数（Fibonacci函数）,Fibonacci数列 无穷数列1，1，2，3，5，8，13，21，34，55， 递归定义为,6,边界条件,递归方程,int fibonacci(int n) if (n = 1) return 1; return fibonacci(n-1)+fibonacci(n-2); ,整数划分问题,定义 将正整数n表示成一系列正整数之和 n=n1+n2+nk， 其中n1n2nk1，k1。 正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。,7,例如正整数6有如下不同的划分： 6； 5+1； 4+2，4+1+1
3、； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1。,整数划分问题,如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系,8,(1) q(n,1)=1,n1; 最大加数n1不大于1，任何正整数n只有一种划分形式，即,(2) q(n,m)=q(n,n),mn; 最大加数n1实际上不能大于n。因此，q(1,m)=1,(3) q(n,n)=1+q(n,n-1); 正整数n的划分由n1=n的划分和n1n-1的划分组成。,(4) q
4、(n,m)=q(n,m-1)+q(n-m,m),nm1; 正整数n的最大加数n1不大于m的划分由n1=m的划分和n1m-1 的划分组成。,整数划分问题,如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系,9,正整数n的划分数p(n)=q(n,n),整数划分问题,例子,10,q(6,3) = q(6,2) + q(3,3),= q(6,1) + q(4,2),+ 1 + q(3,2),= q(6,1) +,+ 1 +,1 + q(2,1),= q(6,1) + q(4,1) +,= 1
5、 + 1 + 1 + 1 + 1 + 1 + 1 = 7,q(4,1) + q(2,2),q(3,1) + q(1,2),+ 1 + q(3,1) + q(1,2),3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1,Hanoi塔问题,设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则： 规则1：每次只能移动1个圆盘； 规则2：任何时刻都不允许将较大的圆盘压在较小的
6、圆盘之上； 规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。,11,Hanoi塔问题,要将n个圆盘按规则从A移动到C，只需 将n1个较小圆盘按规则从A移动到B 将最大的圆盘从A移动到C 将n-1个较小圆盘从B移动到C n个圆盘的移动问题可以转换为 两次n-1个圆盘移动的问题一个单一圆盘移动,12,Hanoi塔问题,void hanoi(int n, int A, int B, int C) if (n 0) hanoi(n-1, A, C, B); move(A, B); hanoi(n-1, C, B, A); hanoi(n, A, B, C)表示将n个圆盘按规则
7、从A移动到B，移动的过程中用C最辅助塔座 move(A, B)表示将A上剩余的单一圆盘从A移动到B,13,函数调用的处理过程,函数A调用函数B时 保存A的所有运行状态 将实参指针、返回地址等信息传递给B 为B中的变量分配存储区 将控制转移到B的入口 从函数B返回到函数A时 保存B的计算结果 释放分配给B的存储区 依照返回地址将控制转移到A,14,递归的处理过程,函数A调用自身 分层：A0, A1, A2, A0调用A1 A1调用A2 A2调用A3 A3返回给A2 A2返回给A1 A1返回给A0,15,A0的运行状态,A1的运行状态,A2的运行状态,A0,A1,A2,A3,递归的特点,优点 结构
8、清晰可读性强 容易用数学归纳法来证明算法的正确性 缺点 递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多,16,消除递归,采用一个用户定义的栈来模拟系统的递归调用工作栈 机械地模拟与递归算法效果相同 根据程序特点对递归调用的工作栈进行简化，减少栈操作,17,18,分治策略,分治策略,分 将要求解的较大规模的问题分割成k个更小规模的子问题。 如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。 治 求解各个子问题 合 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,19
9、,原始问题,求解子问题,子问题,子问题,子问题,求解子问题,求解子问题,子问题解,子问题解,子问题解,合并子解,问题分解,分,治,合,原始问题的解,分治策略,如何分？ 应该把原问题划分为多少个子问题？ 每个子问题的规模是否相同？ 从大量实践中发现，最好使子问题的规模大致相同 许多问题可以取k=2,21,合并排序算法,输入：a1, , n 输出：a1, , n 满足 a0 a1 an 基本思想: 将待排序元素分为大小相等的两个子集合 分别对两个子集合排序 将排好序的子集合合并为最终结果,22,合并排序算法,23,void MergeSort(Type a, int left, int right
10、) 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 ,Merge(a, b, left, i, right): 将排好序的aleft, , i和ai+1, , right按顺序合并到数组b中,合并排序算法,时间复杂性T(n) Merge和Copy可以在O(n)时间内完成,24,合并排序算法,消除递归 首先将
11、a中相邻的元素两两配对 用合并算法将它们排序，构成n/2个长度为2的排好序的数组 再用合并算法将它们排序成n/4个长度4的排好序数组,25,void MergeSort(Type a, int n) int i=1; while(in) 对a进行一边扫描，将a中大小为i的相邻数组合并； ,合并排序算法,运行例子,26,分治策略的时间复杂性,假设分治方法将原问题分解为k个规模为n/m的子问题来求解，则 其中，f (n)为将原问题分解为k个子问题及将k个子问题的解合并为原问题的解所需要的时间,27,二分搜索算法,解决查找元素问题 输入：已经按升序排好序的数组a0,n-1, 某个元素x 输出：x在a
12、中的位置,28,该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题; 分解出的子问题的解可以合并为原问题的解； 分解出的各个子问题是相互独立的。,二分搜索算法,29,比较x和a的中间元素amid 若x=amid，则x在L中的位置就是mid； 如果xai，同理我们只要在amid的后面查找x即可。 无论是在前面还是后面查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。,二分搜索算法,30,据此容易设计出二分搜索算法： int BinarySearch(Type a, const Type ,算法复杂度分析： 每执行一次算法的while循环， 待搜索
13、数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn) 次。循环体内运算需要O(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn) 。,大整数乘法,计算两个n位整数的乘积,31,小学生方法：O(n2) 效率太低 分治法1:,X =,a,b,c,d,X = a 2n/2 + b Y = c 2n/2 + d XY = ac 2n + (ad+bc) 2n/2 + bd,Y =,复杂度分析 T(n)=O(n2) 没有改进,大整数乘法,为了降低时间复杂度，必须减少乘法的次数。 分治法2 XY = ac 2n + (ad+bc) 2n/2 + bd ac 2n
14、+ (a-c)(b-d)+ac+bd) 2n/2 + bd,32,复杂度分析 T(n)=O(nlog3) =O(n1.59)较大的改进,大整数乘法,33,小学生方法：O(n2) 效率太低 分治法: O(n1.59) 较大的改进 更快的方法?,如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。,Strassen矩阵乘法,问题 输入：nn的矩阵A和B 输出：C=AB 简单方法 复杂性O(n3),34,Strassen矩阵乘法,简单分治 使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：,35,复杂度分析 T(n)=
15、O(n3),Strassen矩阵乘法,为了降低时间复杂度，必须减少乘法的次数。 Strassen分治,36,复杂度分析 T(n)=O(nlog7) =O(n2.81)较大的改进,Strassen矩阵乘法,37,传统方法：O(n3) 分治法: O(n2.81) 更快的方法?,Hopcroft和Kerr已经证明(1971)，计算2个矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算22矩阵的7次乘法这样的方法了。或许应当研究或矩阵的更好算法。 在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.376) 是否能找到O(n2)的算法？,快速排序,对数组ap : r进行排序 分：以ap=x为基准将ap : r划分为3段 ap : q-1, aq, aq+1 : r aq=x ap : q-1中的元素小于等于aq aq+1 : r中的元素大于等于aq 治：递归调用快速排序算法对ap : q-1和aq+1 : r排序 合：,38,快速排序,39,void QuickSort (Type a, int p, int r) if (pr) int q = Partition(a,p,r); QuickSort (a,p,q-1); /对左半段排序 QuickSort (a,q+1,r); /对右半段排序
