第2章递归与分治策略优秀PPT.ppt

《第2章递归与分治策略优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第2章递归与分治策略优秀PPT.ppt（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、)T(n/2)T(n/2)T(n)=对这对这k k个子问题分别求解。如果子问题的规模仍然不够小，个子问题分别求解。如果子问题的规模仍然不够小，则再划分为则再划分为k k个子问题，如此递归的进行下去，直到问题规模个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。足够小，很容易求出其解为止。现在学习的是第3页，共54页算法总体思想算法总体思想对这对这k k个子问题分别求解。如果子问题的规模仍然不够小，个子问题分别求解。如果子问题的规模仍然不够小，则再划分为则再划分为k k个子问题，如此递归的进行下去，直到问题规模个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为

3、止。足够小，很容易求出其解为止。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(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、步求出原来问题的解。现在学习的是第4页，共54页算法总体思想算法总体思想将求出的小规模的问题的解合并为一个更大规模的问题的解，自将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。底向上逐步求出原来问题的解。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(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)

5、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(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

6、/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页，共54页2.1 2.1 递归的概念递归的概念直接或间接地调用自身的算法称为直接或间接地调用自身的算法称为递归算法。用函数自身给出定。用函数自身给出定义的函数称为义的函数称为递归函数。由分治法产生的子问题往往是原

7、问题的较小模式，这就为使用递归由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。并由此产生许多高效算法。现在学习的是第7页，共54页递归举例

8、递归举例例1 阶乘函数阶乘函数可递归地定义为：阶乘函数可递归地定义为：边界条件边界条件递归方程递归方程边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。现在学习的是第8页，共54页现在学习的是第9页，共54页递归举例递归举例例2 Fibonacci数列无穷数列无穷数列1 1，1 1，2 2，3 3，5 5，8 8，1313，2121，3434，5555，被称，被称为为FibonacciFibonacci数列。它可以递归地定义为：数列。它可以递归地定义为：边界条件边界条件递归方程递归方程第n个Fibonacci数可递归地计算如下：public st

9、atic int fibonacci(int n)if(n=1)return 1;return fibonacci(n-1)+fibonacci(n-2);现在学习的是第10页，共54页递归小结递归小结优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。现在学习的是第11页，共54页递归小结递归小结解决方法：在递归算法中消除递归调用，使其转化为非递归算法。1.采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了

10、本来由编译器做的事情，优化效果不明显。2.用递推来实现递归函数。3.通过Cooper变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。后两种方法在时空复杂度上均有较大改善，但其适用范围有限。现在学习的是第12页，共54页2.2 分治法分治法学习分治法的策略，合理结合递归学习分治法的策略，合理结合递归求解问题，提高算法效率。求解问题，提高算法效率。现在学习的是第13页，共54页分治策略分治策略分治法的基本思想是将一个规模为分治法的基本思想是将一个规模为n的问题的问题分解为分解为k个规模较小的子问题，这些子问题个规模较小的子问题，这些子问题互相独立且与且与原问题相同。鉴于互相独立和与原问题

11、相同，所以可以鉴于互相独立和与原问题相同，所以可以利用递归的解这些子问题，然后将各子问利用递归的解这些子问题，然后将各子问题的解合并得到原问题的解。题的解合并得到原问题的解。分治法与递归紧密关联。分治法与递归紧密关联。现在学习的是第14页，共54页分割原则：分割原则：人们从大量实践中发现，在用分治法设计算法时，最好人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等使子问题的规模大致相同。即将一个问题分成大小相等的的k k个子问题的处理方法是行之有效的。这种使子问题规个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种模大致相等的

12、做法是出自一种平衡(balancing)子问题的的思想，它几乎总是比子问题规模不等的做法要好。思想，它几乎总是比子问题规模不等的做法要好。现在学习的是第15页，共54页分治法的复杂性分析分治法的复杂性分析一个分治法将规模为n的问题分成k个规模为nm的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：通过迭代法求得方程的解：注意注意：递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)

13、足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当minmi+1时，T(mi)T(n)T(mi+1)。现在学习的是第16页，共54页分治法的适用条件分治法的适用条件分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大

14、部分问题满足这个特征。这条特征是应用分治法的前提，它也是大多数问题可以满足这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用的，此特征反映了递归思想的应用能否利用分治法完全取决于问题是否具有这条特征，如果具能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑备了前两条特征，而不具备第三条特征，则可以考虑贪心贪心算法算法或或动态规划动态规划。这条特征涉及到分治法的效率，如果各子问题是不独这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公立的，则分治法要做许多不必要的工作，重复地

15、解公共的子问题，此时虽然也可用分治法，但一般用共的子问题，此时虽然也可用分治法，但一般用动态动态规划规划较好。较好。现在学习的是第17页，共54页通过例子来理解分治法通过例子来理解分治法二分搜索二分搜索提高效率？提高效率？减小规模？减小规模？现在学习的是第18页，共54页二分搜索技术二分搜索技术分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件分析：比较x和a的中间元素amid，若x=amid，则x在L中的位置就是mid；如果xai，同理我们只要在amid的后面查找x即可。无论是在前面还是后面查找x，其方法都和在a中查找x一样，

16、只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。分析：分析：很显然此问题分解出的子问题相互独立，即在很显然此问题分解出的子问题相互独立，即在ai的前面或后的前面或后面查找面查找x是独立的子问题，因此满足分治法的第四个适用条件。是独立的子问题，因此满足分治法的第四个适用条件。问题：给定已按升序排好序的问题：给定已按升序排好序的n个元素个元素a0:n-1，现要在这，现要在这n个元素中找出个元素中找出一特定元素一特定元素x。分析：分析：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的

17、各个子问题是相互独立的。现在学习的是第19页，共54页算法复杂度分析：每执行一次算法的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn)次。循环体内运算需要O(1)时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn)。现在学习的是第20页，共54页时间复杂性时间复杂性O(n)O(logn)例如：例如：n=1010思考题：求数组的最大值和最小值。思考题：求数组的最大值和最小值。思考题：求数组的最大值和最小值。思考题：求数组的最大值和最小值。思考：利用递归真的比直接求最大值、最小值的效率高吗思考：利用递归真的比直接求最大值、最小值的效率高吗

18、思考：利用递归真的比直接求最大值、最小值的效率高吗思考：利用递归真的比直接求最大值、最小值的效率高吗？现在学习的是第21页，共54页再看分治算法再看分治算法一般，分治算法常与递归方式结合；一般，分治算法常与递归方式结合；一般，将问题分成两个子问题更合理，对一般，将问题分成两个子问题更合理，对于递归来说，分得太细对于效率和复杂性于递归来说，分得太细对于效率和复杂性并无好处。并无好处。现在学习的是第22页，共54页通过例子来理解分治法通过例子来理解分治法大整数乘法大整数乘法提高效率？提高效率？乘法减少？乘法减少？现在学习的是第23页，共54页问题：问题：X和和Y都是都是n位的二进制整数，要计算他们

19、的乘积位的二进制整数，要计算他们的乘积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位的整数乘法；位的整数乘法；加法次数：加法次数：3次整数加法；次整数加法；移位次数：移位次数：2次；次；当当n1时，有时，有T(n)=4T(n/2)+O(n)T(n)=O(n2)算法复

20、杂度：算法复杂度：与小学算法没有改变与小学算法没有改变现在学习的是第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页大整数的乘法大整数的乘法 请设计一个有效的算法，可以进行两个请设计一个有效的算法，可以进行两个n n位大整数的乘法运算位大整数的乘法运算u小学的

21、方法：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,b+d可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。现在学习的是第27页，共54页大整数的乘法大整数的乘法 请设计一个有效的算

22、法，可以进行两个请设计一个有效的算法，可以进行两个n n位大整数的乘法运算位大整数的乘法运算u小学的方法：O(n2)效率太低u分治法:O(n1.59)较大的改进u更快的方法?如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。最终的，这个思想导致了快速傅利叶变换快速傅利叶变换(Fast Fourier Transform)的产生。该方法也可以看作是一个复杂的分治算法，对于大整数乘法，它能在O(nlogn)时间内解决。是否能找到线性时间的算法？目前为止还没有结果。现在学习的是第28页，共54页通过例子来理解分治法通过例子来理解分治法Strassen矩阵乘法矩阵乘法提高效

23、率？提高效率？乘法减少？乘法减少？现在学习的是第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页StrassenStrassen矩阵乘法矩阵乘法使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将

24、方程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更快的方法?Hopcroft和Kerr已经证明(1971)，计算2个矩

25、阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算22矩阵的7次乘法这样的方法了。或许应当研究或矩阵的更好算法。在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.376)是否能找到O(n2)的算法？目前为止还没有结果。现在学习的是第33页，共54页通过例子来理解分治法通过例子来理解分治法合并排序合并排序分治法在排序中的应用！分治法在排序中的应用！现在学习的是第34页，共54页引子：插入排序引子：插入排序现在学习的是第35页，共54页现在学习的是第36页，共54页插入排序的复杂性分析插入排序的复杂性分析O(n

26、2)在这个算法中，大部分的时间都用在挪动在这个算法中，大部分的时间都用在挪动元素中，随着已经排好顺序的数组的增长，元素中，随着已经排好顺序的数组的增长，被挪动的元素的个数也在增加，而且在整被挪动的元素的个数也在增加，而且在整个过程中，很多元素不止挪动一次。个过程中，很多元素不止挪动一次。思考：如何用分治的思想解决问题？思考：如何用分治的思想解决问题？思考：如何用分治的思想解决问题？思考：如何用分治的思想解决问题？现在学习的是第37页，共54页基本思想基本思想当当n=1时，终止排序时，终止排序否则，将待排序元素分成两个大小大致相否则，将待排序元素分成两个大小大致相同的子集和；（递归）同的子集和；

27、（递归）分别对两个子集合进行排序。（分别对两个子集合进行排序。（最终将排好序的子集合合并成为所需的排最终将排好序的子集合合并成为所需的排好序的集合。好序的集合。现在学习的是第38页，共54页现在学习的是第39页，共54页合并排序的灵活革新合并排序的灵活革新首先将长度为首先将长度为1的的n个数组相邻元素两两配对，构成了长个数组相邻元素两两配对，构成了长度为度为2的的n/2个数组，合并时用比较算法对这每个子数组中元个数组，合并时用比较算法对这每个子数组中元素进行排序；素进行排序；再将这些长度为再将这些长度为2的的n/2个数组两两合并，构成了长度为个数组两两合并，构成了长度为4，个数为个数为n/4的

28、子数组，合并时用比较算法对每个子数组元素的子数组，合并时用比较算法对每个子数组元素排序。排序。继续继续直到形成长度为直到形成长度为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 65 76

29、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;/取中点 mer

30、geSort(a,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，修改，修改合并排序算法，求出该有序表的逆合并排序算法，求出该有序表的逆序对数。序对数

31、。现在学习的是第47页，共54页自然排序法自然排序法 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页现在学习的是第

32、52页，共54页现在学习的是第53页，共54页private static 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页