递归与分治策略精选文档.ppt

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

1、递归与分治策略本讲稿第一页，共三十八页 学习要点学习要点:n理解递归的概念。n掌握设计有效算法的分治策略。n通过下面的范例学习分治策略设计技巧。（1）二分搜索技术；（2）合并排序和快速排序；主要内容主要内容:n2.0 分治法总体思想n2.1 递归：阶乘、Fibonacci和Hanoin2.2 分治法的适用条件,基本步骤,复杂性分析n2.3 二分搜索技术n2.4 快速排序n2.5 合并排序n总结本讲稿第二页，共三十八页 将要求解的较大规模的问题分割成k个更小规模的子问题。2.0 分治法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n

2、)=对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。本讲稿第三页，共三十八页2.0 算法总体思想n对这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(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)

3、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将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。本讲稿第四页，共三十八页2.0 算法总体思想n将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。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)

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)本讲稿第五页，共三十八页2.0 算法总体思想n将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。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

5、(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)分治法的设计思想是，将一个难以直接解决的大问题，分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分分割成一些规模较小的相同问题，以便各个击破，分而治之。而治之。本讲稿第六页，共三十八页2.1 递归的概念n直接或间接地调用自身的算法称为递归算法递归算法。用函数自身给出定义的函数称为递归函数递归函数。n由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一

6、致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。n分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。下面来看几个实例。本讲稿第七页，共三十八页2.1 递归的概念例例1 1 阶乘函数阶乘函数 阶乘函数可递归地定义为：边界条件边界条件递归方程递归方程边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。本讲稿第八页，共三十八页2.1 递归的概念例例2 Fibonacci2 Fibonacci数列数列无穷数列1，1，2，3，5，8，13，21，34，55，称为Fibonacci数列。它可以递

7、归地定义为：边界条件边界条件递归方程递归方程第n个Fibonacci数可递归地计算如下：int fibonacci(int n)if(n=1)return 1;return fibonacci(n-1)+fibonacci(n-2);本讲稿第九页，共三十八页例例2 Fibonacci调用结构：调用结构：本讲稿第十页，共三十八页例例2 Fib复杂度分析：The call tree is a full binary tree down to depth n/2,the rightmost path being the shortest,such as n,n-2,0.(n is even).The

8、refore,the running time is at least O(2n/2)本讲稿第十一页，共三十八页Modify the procedure of Example 2,whichcomputes Fibonacci numbers,to use only aconstant numbers for work space and still computeFn in O(n)time.nif(n=1)return n;nprev2=0;prev1=1;nfor(i=2;i 0)hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);本讲稿第十四页，共三

9、十八页2.1 递归小结优点：优点：结构清晰，可读性强，而且容易用数学结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。法、调试程序带来很大方便。缺点：缺点：递归算法的运行效率较低，无论是耗费递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算的计算时间还是占用的存储空间都比非递归算法要多。法要多。本讲稿第十五页，共三十八页解决方法：解决方法：在递归算法中消除递归调用，使其转化为在递归算法中消除递归调用，使其转化为非递归算法。非递归算法。1 1、采用一个用户定义的栈来模拟系统的递归调用

10、工、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。人工做了本来由编译器做的事情，优化效果不明显。2 2、用递推来实现递归函数。反向递归、用递推来实现递归函数。反向递归3 3、通过变换能将一些递归转化为尾递归，从而迭、通过变换能将一些递归转化为尾递归，从而迭代求出结果。反演变换代求出结果。反演变换 后两种方法在时空复杂度上均有较大改善，但后两种方法在时空复杂度上均有较大改善，但其适用范围有限。其适用范围有限。2.1 递归小结本讲稿第十六页，共三十八页2.2 分治法

11、的适用条件分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：n该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；n该问题可以分解为若干个该问题可以分解为若干个规模较小的相同规模较小的相同问题，即该问题具有问题，即该问题具有最优子结构性质最优子结构性质n利用该问题分解出的子问题的解利用该问题分解出的子问题的解可以合并可以合并为该问题的解；为该问题的解；n该问题所分解出的各个子问题是该问题所分解出的各个子问题是相互独立的相互独立的，即子问题

12、之间，即子问题之间不包含公共的子问题。不包含公共的子问题。因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法贪心算法或动态规划动态规划。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规动态规划划较好。本讲稿第十七页，共三十八页divide-and-conquer(P)if(|P|=n0)a

13、dhoc(P);/解决小规模的问题 divide P into smaller subinstances P1,P2,.,Pk；/分解问题 for(i=1,i=k,i+)yi=divide-and-conquer(Pi);/递归的解各子问题 return merge(y1,.,yk);/将各子问题的解合并为原问题的解 2.2 分治法的基本步骤人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡平衡(balancing)子问题子问题的思想，它几乎总是比子问题规模不等的做法要

14、好。本讲稿第十八页，共三十八页2.2 分治法的复杂性分析一个分治法将规模为n的问题分成k个规模为nm的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用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(

15、mi+1)。本讲稿第十九页，共三十八页分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件分析：比较x和a的中间元素amid，若x=amid，则x在L中的位置就是mid；如果xai，同理我们只要在amid的后面查找x即可。无论是在前面还是后面查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。分析：很显然此问题分解出的子问题相互独立，即在ai的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。2.3 二分搜索技术给定已按升序排好序的给定已按升序排好序的n个

16、元素个元素a0:n-1，现要在这，现要在这n个元素中找出一个元素中找出一特定元素特定元素x。分析：分析：n该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；n该问题可以分解为若干个规模较小的相同问题该问题可以分解为若干个规模较小的相同问题;n分解出的子问题的解可以合并为原问题的解；分解出的子问题的解可以合并为原问题的解；n分解出的各个子问题是相互独立的。分解出的各个子问题是相互独立的。本讲稿第二十页，共三十八页2.3 二分搜索技术给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要在这，现要在这n个元素中找出一特个元素中找出一特定元

17、素定元素x。据此容易设计出二分搜索算法二分搜索算法：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 am)r=m-1;else l=m+1;return-1;算法复杂度分析：算法复杂度分析：每执行一次算法的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn)次。循环体内运算需要O(1)时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn)。本讲稿第二十一页，共三十八页2.4 Quic

18、ksortnQuicksort Strategy:通过一趟排序将待排序记录分割成独立的两部分，其中一部分的关键字均比另一部分的关键字小，然后分别对这两部分记录递归地继续分别进行排序，以达到整个序列有序。n C.A.R.Hoare(Tony Hoare)教授，1980年获得美国计算机学会(ACM)设立的计算机界最高奖图灵奖 本讲稿第二十二页，共三十八页2.4 快速排序在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。templatevoid QuickSort(T

19、ype a,int p,int r)if(pr)int q=Partition(a,p,r);QuickSort(a,p,q-1);/对左半段排序 QuickSort(a,q+1,r);/对右半段排序 本讲稿第二十三页，共三十八页templateint Partition(Type a,int p,int r)int i=p+1,j=r;Type x=ap;/将 x的元素交换到右边区域 while(true)while(ai x)j-;if(i=j)break;Swap(ai,aj)i+;j-;ap=aj;aj=x;return j;2.4 快速排序快速排序:Partition方法方法1正确吗

20、正确吗?本讲稿第二十四页，共三十八页2.4 一趟快速排序的算法是：Partition方法方法21）设置两个变量I、J，排序开始的时候：I=0，J=N-1；2）以第一个数组元素作为关键数据，赋值给key，即 key=A0；3）从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于key的值AJ，并与AI交换；4）从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于key的AI，与AJ交换；5）重复第3、4、5步，直到 I=J；(3,4步是在程序中没找到时候j=j-1，i=i+1。找到并交换的时候i，j指针位置不变。另外当i=j这过程一定正好是i+或j+完成的最后另循环结

21、束)本讲稿第二十五页，共三十八页2.4 Quicksort:example初始关键字：初始关键字：4949，3838，6565，9797，7676，1313，2727，4949 pivot key 4949jji1 1次交换后：次交换后：2727，3838，6565，9797，7676，1313，4949 iji2 2次交换后：次交换后：2727，3838，9797，7676，1313，6565，4949 ijj3 3次交换后：次交换后：2727，3838，1313，9797，7676，6565，4949 iji4 4次交换后：次交换后：2727，3838，1313，7676，9797，656

22、5，4949 jij一趟完成后：一趟完成后：2727，3838，1313，4949，7676，9797，6565，4949 本讲稿第二十六页，共三十八页2.4 Analysis of Quicksort:worst case情况：划分后产生的两区域分别包含n-1和1个元素本讲稿第二十七页，共三十八页2.4 Analysis of Quicksort:average behavior 方法1本讲稿第二十八页，共三十八页2.4 Analysis of Quicksort:average behavior：方法1本讲稿第二十九页，共三十八页2.4 Analysis of Quicksort:aver

23、age behavior 方法2可得其解：T(n)=O(nlogn)本讲稿第三十页，共三十八页2.5 合并排序基本思想：基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。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,lef

24、t,right);/复制回数组a 本讲稿第三十一页，共三十八页2.5 合并排序算法mergeSort的递归过程可以消去。重点讲Merge的过程，参考教材P36。初始序列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 97本讲稿第三十二页，共三十八页2.5 复杂度分析：W(n)=W(n/2)+W(n/2)+Wmerge(n)(n log n)Wmerge(n)=n-1W(1)=0本讲稿第三十三页，共三十八页2.5 Worst Case Behavior本讲稿第三十四页，共

25、三十八页2.5合并排序n平均时间复杂度：平均时间复杂度：O(nlogn)复杂度分析复杂度分析T(n)=O(nlogn)渐进意义下的最优算法本讲稿第三十五页，共三十八页2.5合并排序合并排序 Ex 4.26n4.26 How many key comparisons are done by Mergesort if the keys are already in order when the sort begins?nIf the keys are already sorted,merging the two halves will need only n/2 comparisons.So the recurrence relation isnFor simplicity,assume that n is a power of 2.Then,by expanding a few terms it is easy to see that本讲稿第三十六页，共三十八页2.5 合并排序&最坏时间复杂度：最坏时间复杂度：O(nlogn)&平均时间复杂度：平均时间复杂度：O(nlogn)&辅助空间：辅助空间：O(n)本讲稿第三十七页，共三十八页总结1、分治法主要思想2、递归：Fibonacci3、排序：快速、合并本讲稿第三十八页，共三十八页