《第2章递归与分治策略精.ppt》由会员分享，可在线阅读，更多相关《第2章递归与分治策略精.ppt（54页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第2章递归与分治策章递归与分治策略略第1页，本讲稿共54页内容提要内容提要理解递归的概念理解递归的概念理解分治法的策略理解分治法的策略学会设计，通过例子学会设计，通过例子二分搜索二分搜索大整数乘法大整数乘法Strassen矩阵乘法矩阵乘法合并排序合并排序快速排序快速排序线性时间选择线性时间选择最接近点对问题最接近点对问题循环赛日程表循环赛日程表总结归纳总结归纳第2页，本讲稿共54页将要求解的较大规模的问题分割成将要求解的较大规模的问题分割成k k个更小规模的子问题。个更小规模的子问题。算法总体思想算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2
2、)T(n/2)T(n)=对这对这k k个子问题分别求解。如果子问题的规模仍然不够小，个子问题分别求解。如果子问题的规模仍然不够小，则再划分为则再划分为k k个子问题，如此递归的进行下去，直到问题规个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。模足够小，很容易求出其解为止。第3页，本讲稿共54页算法总体思想算法总体思想对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(
3、n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)将求出的小规模的问题的解合并为一个更大规模的问题的解，将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。自底向上逐步求出原来问题的解。第4页，本讲稿共54页算法总体思想算法总体思想将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(
4、n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)第5页，本讲稿共54页算法总体思想算法总体思想将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T
5、(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)分治法的设计思想是，将一个难以直接解决的大问题，分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分割成一些规模较小的相同问题，以便各个击破，分而治之。分而治之。凡治众如治寡，分数是也。凡治众如
6、治寡，分数是也。-孙子兵法孙子兵法第6页，本讲稿共54页2.1 2.1 递归的概念递归的概念直接或间接地调用自身的算法称为直接或间接地调用自身的算法称为递归算法。用函数自身给出。用函数自身给出定义的函数称为定义的函数称为递归函数。由分治法产生的子问题往往是原问题的较小模式，这就为使用由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过
7、程的产生。问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。由此产生许多高效算法。第7页，本讲稿共54页递归举例递归举例例1 阶乘函数阶乘函数可递归地定义为：阶乘函数可递归地定义为：边界条件边界条件递归方程递归方程边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。第8页，本讲稿共54页第9页，本讲稿共54页递归举例递归举例例2 Fibonacci数列无穷数列无穷数列1 1，1 1，2 2，3 3，5 5，8
8、8，1313，2121，3434，5555，被称为，被称为FibonacciFibonacci数列。它可以递归地定义为：数列。它可以递归地定义为：边界条件边界条件递归方程递归方程第n个Fibonacci数可递归地计算如下：public static int fibonacci(int n)if(n=1)return 1;return fibonacci(n-1)+fibonacci(n-2);第10页，本讲稿共54页递归小结递归小结优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用
9、的存储空间都比非递归算法要多。第11页，本讲稿共54页递归小结递归小结解决方法：在递归算法中消除递归调用，使其转化为非递归算法。1.采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。2.用递推来实现递归函数。3.通过Cooper变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。后两种方法在时空复杂度上均有较大改善，但其适用范围有限。第12页，本讲稿共54页2.2 分治法分治法学习分治法的策略，合理结合递归学习分治法的策略，合理结合递归求解问题，提高算法效率。求解问题，提高算法效率。第13页，本讲稿共54
10、页分治策略分治策略分治法的基本思想是将一个规模为分治法的基本思想是将一个规模为n的问题的问题分解为分解为k个规模较小的子问题，这些子问题个规模较小的子问题，这些子问题互相独立且与且与原问题相同。鉴于互相独立和与原问题相同，所以可以鉴于互相独立和与原问题相同，所以可以利用递归的解这些子问题，然后将各子问利用递归的解这些子问题，然后将各子问题的解合并得到原问题的解。题的解合并得到原问题的解。分治法与递归紧密关联。分治法与递归紧密关联。第14页，本讲稿共54页分割原则：分割原则：人们从大量实践中发现，在用分治法设计算法时，人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一
11、个问题分成最好使子问题的规模大致相同。即将一个问题分成大小相等的大小相等的k k个子问题的处理方法是行之有效的。这种个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模的思想，它几乎总是比子问题规模不等的做法要好。不等的做法要好。第15页，本讲稿共54页分治法的复杂性分析分治法的复杂性分析一个分治法将规模为n的问题分成k个规模为nm的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原
12、问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：通过迭代法求得方程的解：注意注意：递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当minmi+1时，T(mi)T(n)T(mi+1)。第16页，本讲稿共54页分治法的适用条件分治法的适用条件分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题
13、具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。这条特征是应用分治法的前提，它也是大多数问题可以满足这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用的，此特征反映了递归思想的应用能否利用分治法完全取决于问题是否具有这条特征，如果具能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑备了前两条特征，而不具备第三条特征，则可以考虑贪心算贪心算法法或或
14、动态规划动态规划。这条特征涉及到分治法的效率，如果各子问题是不独立这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用子问题，此时虽然也可用分治法，但一般用动态规划动态规划较较好。好。第17页，本讲稿共54页通过例子来理解分治法通过例子来理解分治法二分搜索二分搜索提高效率？提高效率？减小规模？减小规模？第18页，本讲稿共54页二分搜索技术二分搜索技术分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件分
15、析：比较x和a的中间元素amid，若x=amid，则x在L中的位置就是mid；如果xai，同理我们只要在amid的后面查找x即可。无论是在前面还是后面查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。分析：分析：很显然此问题分解出的子问题相互独立，即在很显然此问题分解出的子问题相互独立，即在ai的前面或后面查的前面或后面查找找x是独立的子问题，因此满足分治法的第四个适用条件。是独立的子问题，因此满足分治法的第四个适用条件。问题：给定已按升序排好序的问题：给定已按升序排好序的n个元素个元素a0:n-1，现要在这，现要在这n个元素中找
16、个元素中找出一特定元素出一特定元素x。分析：分析：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。第19页，本讲稿共54页算法复杂度分析：每执行一次算法的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn)次。循环体内运算需要O(1)时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn)。第20页，本讲稿共54页时间复杂性时间复杂性O(n)O(logn)例如：例如：n=1010思考题：求数组的最大值和最小值。思考题：求数组的最大值
17、和最小值。思考题：求数组的最大值和最小值。思考题：求数组的最大值和最小值。思考：利用递归真的比直接求最大值、最小值的效率高思考：利用递归真的比直接求最大值、最小值的效率高思考：利用递归真的比直接求最大值、最小值的效率高思考：利用递归真的比直接求最大值、最小值的效率高吗？吗？吗？吗？第21页，本讲稿共54页再看分治算法再看分治算法一般，分治算法常与递归方式结合；一般，分治算法常与递归方式结合；一般，将问题分成两个子问题更合理，对一般，将问题分成两个子问题更合理，对于递归来说，分得太细对于效率和复杂性于递归来说，分得太细对于效率和复杂性并无好处。并无好处。第22页，本讲稿共54页通过例子来理解分治
18、法通过例子来理解分治法大整数乘法大整数乘法提高效率？提高效率？乘法减少？乘法减少？第23页，本讲稿共54页问题：问题：X和和Y都是都是n位的二进制整数，要计算他们的乘积位的二进制整数，要计算他们的乘积XY。分治法：将分治法：将n位的二进制整数位的二进制整数X和和Y都分成都分成2段，每段的段，每段的长为长为n/2位。位。所以，所以，X=A2n/2+B,Y=C2n/2+DXY=AC 2n+(AD+BC)2n/2+BD 大整数的乘法大整数的乘法第24页，本讲稿共54页算法复杂性分析算法复杂性分析XY=AC 2n+(AD+BC)2n/2+BD乘法次数：乘法次数：4次次n/2位的整数乘法；位的整数乘法；
19、加法次数：加法次数：3次整数加法；次整数加法；移位次数：移位次数：2次；次；当当n1时，有时，有T(n)=4T(n/2)+O(n)T(n)=O(n2)算法复杂度：算法复杂度：与小学算法没有改变与小学算法没有改变第25页，本讲稿共54页再接再厉再接再厉XY=AC 2n+(AD+BC)2n/2+BDXY=AC 2n+(A-B)(D-C)+AC+BD)2n/2+BD乘法次数：乘法次数：3次次n/2位的整数乘法；位的整数乘法；加法：加法：6次整数加法；次整数加法；移位：移位：2次次当当n1时，有时，有T(n)=3T(n/2)+O(n)T(n)=O(nlog3)=O(n1.59)第26页，本讲稿共54页
20、大整数的乘法大整数的乘法 请设计一个有效的算法，可以进行两个请设计一个有效的算法，可以进行两个n n位大整数的乘法运算位大整数的乘法运算u小学的方法：O(n2)效率太低u分治法:XY=ac 2n+(ad+bc)2n/2+bd 为了降低时间复杂度，必须减少乘法的次数。为了降低时间复杂度，必须减少乘法的次数。1.XY=ac 2n+(a-c)(b-d)+ac+bd)2n/2+bd2.XY=ac 2n+(a+c)(b+d)-ac-bd)2n/2+bd复杂度分析复杂度分析T(n)=O(nlog3)=O(n1.59)较大的改进较大的改进细节问题细节问题：两个XY的复杂度都是O(nlog3)，但考虑到a+c
21、,b+d可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。第27页，本讲稿共54页大整数的乘法大整数的乘法 请设计一个有效的算法，可以进行两个请设计一个有效的算法，可以进行两个n n位大整数的乘法运算位大整数的乘法运算u小学的方法：O(n2)效率太低u分治法:O(n1.59)较大的改进u更快的方法?如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。最终的，这个思想导致了快速傅利叶变换快速傅利叶变换(Fast Fourier Transform)的产生。该方法也可以看作是一个复杂的分治算法，对于大整数乘法，它能在O(nlogn)时间内解决。是否能找到线性时
22、间的算法？目前为止还没有结果。第28页，本讲稿共54页通过例子来理解分治法通过例子来理解分治法Strassen矩阵乘法矩阵乘法提高效率？提高效率？乘法减少？乘法减少？第29页，本讲稿共54页Strassen Strassen 矩阵乘法矩阵乘法A和B的乘积矩阵C中的元素Ci,j定义为:若依此定义来计算若依此定义来计算A和和B的乘积矩阵的乘积矩阵C，则每计算，则每计算C的的一个元素一个元素Cij，需要做，需要做n次乘法和次乘法和n-1次加法。因此，次加法。因此，算出矩阵算出矩阵C的的 个元素所需的计算时间为个元素所需的计算时间为O(n3)u传统方法：O(n3)第30页，本讲稿共54页Strasse
23、nStrassen矩阵乘法矩阵乘法使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：u传统方法：O(n3)u分治法:由此可得：复杂度分析复杂度分析T(n)=O(n3)没有改进没有改进第31页，本讲稿共54页StrassenStrassen矩阵乘法矩阵乘法u传统方法：O(n3)u分治法:为了降低时间复杂度，必须减少乘法的次数。复杂度分析复杂度分析T(n)=O(nlog7)=O(n2.81)较大的改进较大的改进第32页，本讲稿共54页StrassenStrassen矩阵乘法矩阵乘法u传统方法：O(n3)u分治法:O(n2.81)u更快的方法?
24、Hopcroft和Kerr已经证明(1971)，计算2个矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算22矩阵的7次乘法这样的方法了。或许应当研究或矩阵的更好算法。在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.376)是否能找到O(n2)的算法？目前为止还没有结果。第33页，本讲稿共54页通过例子来理解分治法通过例子来理解分治法合并排序合并排序分治法在排序中的应用！分治法在排序中的应用！第34页，本讲稿共54页引子：插入排序引子：插入排序第35页，本讲稿共54页第36页，本讲稿共54页插入排序的复
25、杂性分析插入排序的复杂性分析O(n2)在这个算法中，大部分的时间都用在挪动在这个算法中，大部分的时间都用在挪动元素中，随着已经排好顺序的数组的增长，元素中，随着已经排好顺序的数组的增长，被挪动的元素的个数也在增加，而且在整被挪动的元素的个数也在增加，而且在整个过程中，很多元素不止挪动一次。个过程中，很多元素不止挪动一次。思考：如何用分治的思想解决问题？思考：如何用分治的思想解决问题？思考：如何用分治的思想解决问题？思考：如何用分治的思想解决问题？第37页，本讲稿共54页基本思想基本思想当当n=1时，终止排序时，终止排序否则，将待排序元素分成两个大小大致相否则，将待排序元素分成两个大小大致相同的
26、子集和；（递归）同的子集和；（递归）分别对两个子集合进行排序。（分别对两个子集合进行排序。（最终将排好序的子集合合并成为所需的排最终将排好序的子集合合并成为所需的排好序的集合。好序的集合。第38页，本讲稿共54页第39页，本讲稿共54页合并排序的灵活革新合并排序的灵活革新首先将长度为首先将长度为1的的n个数组相邻元素两两配对，构成了长度为个数组相邻元素两两配对，构成了长度为2的的n/2个数组，合并时用比较算法对这每个子数组中元素进个数组，合并时用比较算法对这每个子数组中元素进行排序；行排序；再将这些长度为再将这些长度为2的的n/2个数组两两合并，构成了长度为个数组两两合并，构成了长度为4，个数
27、为，个数为n/4的子数组，合并时用比较算法对每个子数组的子数组，合并时用比较算法对每个子数组元素排序。元素排序。继续继续直到形成长度为直到形成长度为n，子数组个数，子数组个数=1的整个数组为止。的整个数组为止。基本思想：基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。第40页，本讲稿共54页合并排序合并排序算法mergeSort的递归过程可以消去。初始序列49 38 65 97 76 13 2738 49 65 97 13 76 27第一步第二步38 49 65 97 13 27 76第三步13 27 38 49
28、65 76 97第41页，本讲稿共54页如何将两个有序段合并成一个有序段？如何将两个有序段合并成一个有序段？第42页，本讲稿共54页第43页，本讲稿共54页第44页，本讲稿共54页第45页，本讲稿共54页合并排序合并排序基本思想：基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。public static void mergeSort(Comparable a,int left,int right)if(leftright)/至少有2个元素 int i=(left+right)/2;/取中点 mergeSort(a,
29、left,i);mergeSort(a,i+1,right);merge(a,b,left,i,right);/合并到数组b copy(a,b,left,right);/复制回数组a 复杂度分析复杂度分析T(n)=O(nlogn)渐进意义下的最优算法第46页，本讲稿共54页合并排序合并排序&最坏时间复杂度：最坏时间复杂度：O(nlogn)&平均时间复杂度：平均时间复杂度：O(nlogn)&辅助空间：辅助空间：O(n)&稳定性：稳定稳定性：稳定思考题：给定有序表思考题：给定有序表A1:n，修改，修改合并排序算法，求出该有序表的逆合并排序算法，求出该有序表的逆序对数。序对数。第47页，本讲稿共54
30、页自然排序法自然排序法 4,8,3,7,1,5,6,24,8,3,7,1,5,6,23,4,7,8,1,2,5,61,2,3,4,5,6,7,8第48页，本讲稿共54页快速排序快速排序分治法的应用分治法的应用第49页，本讲稿共54页基本思想基本思想对于输入的子数组对于输入的子数组ap:r,按三个步骤按三个步骤分解：以分解：以ap为基准元素，将为基准元素，将ap:r划分成划分成3段段 ap:q-1,aq和和aq+1:r递归求解：分别对两端进行排序递归求解：分别对两端进行排序合并合并第50页，本讲稿共54页第51页，本讲稿共54页第52页，本讲稿共54页第53页，本讲稿共54页private st
31、atic int randomizedPartition(int p,int r)int i=random(p,r);MyMath.swap(a,i,p);return partition(p,r);快速排序快速排序 快速排序算法的性能取决于划分的对称性。通过修改算法partition，可以设计出采用随机选择策略的快速排序算法。在快速排序算法的每一步中，当数组还没有被划分时，可以在ap:r中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。&最坏时间复杂度：最坏时间复杂度：O(n2)&平均时间复杂度：平均时间复杂度：O(nlogn)&辅助空间：辅助空间：O(n)或或O(logn)&稳定性：不稳定稳定性：不稳定第54页，本讲稿共54页