递归与分治策略

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

2、n)= 对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。第3页，共38页，2022年，5月20日，19点36分，星期三2.0 算法总体思想对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 将求出的小规

3、模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。第4页，共38页，2022年，5月20日，19点36分，星期三2.0 算法总体思想将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)第5页，共38页，2022年，5月20日，19点36分，星期三2.0 算法总体思想将求出的小规模的问题的解合并为一个更大规模的问题的解

4、，自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。第6页，共38页，2022年，5月20日，19点36分，星期三2.1 递归的概念直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这

5、种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。下面来看几个实例。第7页，共38页，2022年，5月20日，19点36分，星期三2.1 递归的概念例1 阶乘函数 阶乘函数可递归地定义为：边界条件递归方程边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。第8页，共38页，2022年，5月20日，19点36分，星期三2.1 递归的概念例2 Fibonacci数列无穷数列1，1，2，3

6、，5，8，13，21，34，55，称为Fibonacci数列。它可以递归地定义为：边界条件递归方程第n个Fibonacci数可递归地计算如下：int fibonacci(int n) if (n = 1) return 1; return fibonacci(n-1)+fibonacci(n-2); 第9页，共38页，2022年，5月20日，19点36分，星期三例2 Fibonacci调用结构：第10页，共38页，2022年，5月20日，19点36分，星期三例2 Fib复杂度分析： The call tree is a full binary tree down to depth n/2, t

7、he rightmost path being the shortest, such as n,n-2,0. (n is even). Therefore, the running time is at least O(2n/2)第11页，共38页，2022年，5月20日，19点36分，星期三Modify the procedure of Example 2, whichcomputes Fibonacci numbers, to use only aconstant numbers for work space and still computeFn in O(n) time.if (n =

8、1) return n;prev2 = 0; prev1 = 1;for (i = 2; i 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); 第14页，共38页，2022年，5月20日，19点36分，星期三2.1 递归小结优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。第15页，共38页，2022年，5月20日，19点36分，星期三解决方法：在递归算法中消除递归调用，使其转化为非递归算法

9、。1、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。2、用递推来实现递归函数。反向递归3、通过变换能将一些递归转化为尾递归，从而迭代求出结果。反演变换 后两种方法在时空复杂度上均有较大改善，但其适用范围有限。2.1 递归小结第16页，共38页，2022年，5月20日，19点36分，星期三2.2 分治法的适用条件分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题

10、的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。第17页，共38页，2022年，5月20日，19点36分，星期三divide-and-con

11、quer(P) if ( | P | = n0) adhoc(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个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancin

12、g)子问题的思想，它几乎总是比子问题规模不等的做法要好。第18页，共38页，2022年，5月20日，19点36分，星期三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)的

13、增长速度。通常假定T(n)是单调上升的，从而当minmi+1时，T(mi)T(n)T(mi+1)。 第19页，共38页，2022年，5月20日，19点36分，星期三分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件分析：比较x和a的中间元素amid，若x=amid，则x在L中的位置就是mid；如果xai，同理我们只要在amid的后面查找x即可。无论是在前面还是后面查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。 分析：很显然此问题分解出的子问题相互独立，即在ai的

14、前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。2.3 二分搜索技术给定已按升序排好序的n个元素a0:n-1，现要在这n个元素中找出一特定元素x。分析：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。 第20页，共38页，2022年，5月20日，19点36分，星期三2.3 二分搜索技术给定已按升序排好序的n个元素a0:n-1，现要在这n个元素中找出一特定元素x。据此容易设计出二分搜索算法：template int BinarySearch(Type a, const

15、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) 。第21页，共38页，2022年，5月20日，19点36分，星期三2.4 QuicksortQuicksort Strategy:

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

17、, int p, int r) if (pr) int q=Partition(a,p,r); QuickSort (a,p,q-1); /对左半段排序 QuickSort (a,q+1,r); /对右半段排序 第23页，共38页，2022年，5月20日，19点36分，星期三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

18、= aj; aj = x; return j; 2.4 快速排序: Partition方法1正确吗?第24页，共38页，2022年，5月20日，19点36分，星期三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步

19、是在程序中没找到时候j=j-1，i=i+1。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j+完成的最后另循环结束) 第25页，共38页，2022年，5月20日，19点36分，星期三2.4 Quicksort: example初始关键字：49，38，65，97，76，13，27，49pivot key 49jji1次交换后：27，38，65，97，76，13， ，49iji2次交换后：27，38， ，97，76，13，65，49ijj3次交换后：27，38，13，97，76， ，65，49iji4次交换后：27，38，13， ，76，97，65，49jij一趟完成后：

20、27，38，13，49，76，97，65，49第26页，共38页，2022年，5月20日，19点36分，星期三2.4 Analysis of Quicksort: worst case情况：划分后产生的两区域分别包含n-1和1个元素第27页，共38页，2022年，5月20日，19点36分，星期三2.4 Analysis of Quicksort: average behavior 方法1第28页，共38页，2022年，5月20日，19点36分，星期三2.4 Analysis of Quicksort: average behavior：方法1第29页，共38页，2022年，5月20日，19点3

21、6分，星期三2.4 Analysis of Quicksort: average behavior 方法2可得其解：T(n)=O(nlogn)第30页，共38页，2022年，5月20日，19点36分，星期三2.5 合并排序基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。 void MergeSort(Type a, int left, int right) if (leftright) /至少有2个元素 int i=(left+right)/2; /取中点 mergeSort(a, left, i); mergeS

22、ort(a, i+1, right); merge(a, b, left, i, right); /合并到数组b copy(a, b, left, right); /复制回数组a 第31页，共38页，2022年，5月20日，19点36分，星期三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第32页，共38页，2022年，5月20日，19点36分，星期三2.5 复杂度分析：W(n) = W(n/2)+W(n/