《第2讲数据结构与算法概要》由会员分享，可在线阅读，更多相关《第2讲数据结构与算法概要（114页珍藏版）》请在金锄头文库上搜索。
1、第2章 递归与分治策略,学习要点: 理解递归的概念。 掌握设计有效算法的分治策略。 通过下面的范例学习分治策略设计技巧。 （1）二分搜索技术； （2）大整数乘法； （3）Strassen矩阵乘法； （4）棋盘覆盖； （5）合并排序和快速排序； （6）线性时间选择； （7）最接近点对问题； （8）循环赛日程表。,将要求解的较大规模的问题分割成k个更小规模的子问题。,算法总体思想,n,T(n/2),T(n/2),T(n/2),T(n/2),T(n),=,对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,算法总体思
2、想,对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,n,T(n),=,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,算法总体思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,n,T(n),=,算法总体思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,分治法的设计思想是，将一个难以直接解决的大问题， 分割成一些规模较小的相同问题，以便各个击破， 分而治之。,2.1 递归的概念,直接或间接
3、地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。 由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。 分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。,2.1 递归的概念,例1 阶乘函数 非递归定义：n！=n*(n-1)*(n-2)*1 阶乘函数可递归地定义为：,边界条件,递归方程,边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。
4、,递归算法： int recur(int n) if (n = 1) return 1; return n*recur(n-1); ,递归出口,递归调用,小兔子问题,一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔都不死，那么一年以后可以繁殖多少对兔子？,经过月数：-1-2-3-4-5-6-7-8-9-10-11-12 兔子对数：-1-1-2-3-5-8-13-21-34-55-89-144,2.1 递归的概念,例2 Fibonacci数列 无穷数列1，1，2，3，5，8，13，21，34，55，称为Fibonacci数列。它可以递归地定义为：,边界条件
5、,递归方程,第n个Fibonacci数可递归地计算如下： int fibonacci(int n) if (n = 1) return 1; return fibonacci(n-1)+fibonacci(n-2); ,Fibonacci(5)的递归求解过程： 2*8-1=15,2.1 递归的概念,例3 Ackerman函数 当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。 Ackerman函数A(n，m)定义如下：,2.1 递归的概念,例3 Ackerman函数 前2例中的函数都可以找到相应的非递归方式定义：,本例中的Ackerman函数却无法找到非递归的定义。,2.1
6、递归的概念,例3 Ackerman函数 A(n，m)的自变量m的每一个值都定义了一个单变量函数： M=0时，A(n,0)=n+2 M=1时，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2*n M=2时，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)= 2n 。 M=3时，类似的可以推出 M=4时，A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数。,2.1 递归的概念,例3 Ackerman函数 定义单变量的Ackerman函数A(n)
7、为，A(n)=A(n，n)。 定义其拟逆函数(n)为：(n)=minkA(k)n。即(n)是使nA(k)成立的最小的k值。 (n)在复杂度分析中常遇到。对于通常所见到的正整数n，有(n)4。但在理论上(n)没有上界，随着n的增加，它以难以想象的慢速度趋向正无穷大。,2.1 递归的概念,例5 整数划分问题 将正整数n表示成一系列正整数之和：n=n1+n2+nk， 其中n1n2nk1，k1。 正整数n的这种表示称为正整数n的划分。求正整数n的不 同划分个数。,例如正整数6有如下11种不同的划分： 6； 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1
8、，2+1+1+1+1； 1+1+1+1+1+1。,(2) q(n,m)=q(n,n),mn; 最大加数n1实际上不能大于n。因此，q(1,m)=1。,(1) q(n,1)=1,n1; 当最大加数n1不大于1时，任何正整数n只有一种划分形式， 即,(4) q(n,m)=q(n,m-1)+q(n-m,m),nm1; 正整数n的最大加数n1不大于m的划分由n1=m的划分和 n1m-1 的划分组成。,(3) q(n,n)=1+q(n,n-1); 正整数n的划分由n1=n的划分和n1n-1的划分组成。,2.1 递归的概念,例5 整数划分问题 前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用
9、递归函数直接求解。 在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。,2.1 递归的概念,例5 整数划分问题 前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。 在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。,正整数n的划分数p(n)=q(n,n)。,2.1 递归的概念,例6 Hanoi塔问题 设a,b,c是3个塔
10、座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则： 规则1：每次只能移动1个圆盘； 规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上； 规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。,以四个盘子为例,移动N个圆盘的过程包括: 2次移动N-1个圆盘的过程 1次移动1个圆盘的过程,void hanoi(int n, int a, int b, int c) if (n 0) hanoi(n-1, a, c, b)
11、; move(a,b); hanoi(n-1, c, b, a); ,Hanoi塔问题的复杂性分析,=1 移动次数（） 移动次数（） 移动次数（） 移动次数（） 当时 移动次数（）？,“世界末日问题”,“世界末日”的推算,假定该僧人每秒将一个圆盘从一个塔座移动到另一个塔座 完成整个工作的时间 64（秒） 18,446,744,073,709,551,615（秒） 5850亿年,算法复杂性同与运算能力的关系,假定一个问题有六种不同的算法，算法复杂度分别是（logn, n, nlogn, n2, 2n, n!) 这六种算法在低速计算机C1和比C1速度快1000倍的计算机C2上运行，N1和N2分别为
12、这六种算法在C1和C2上的可解规模,递归小结,优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。,缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。,求Fibonacci数时有很多重复工作：,解决方法：在递归算法中消除递归调用，使其转化为非递归算法。 1、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。 2、用递推来实现递归函数。 3、通过变换能将一些递归转化为尾递归，从而迭代求出结果。 后两种方法在时空复杂度上均有
13、较大改善，但其适用范围有限。,递归小结,分治法的基本思想,分治法的基本思想 将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立并且与原问题相同。通过递归地求解这些子问题，然后再将各个子问题的解合并，就可以实现对原问题的求解。,分治法的求解过程,分治法的求解过程 分解(divide)：将原问题分解为一系列子问题； 递归求解(conquer)：递归求解各个子问题。若子问题足够小，则直接求解。 合并(merge)：将子问题结果合并成原问题的解 说明：某些问题不需要合并，比如二分搜索问题,divide-and-conquer(P) if(|P|=n0) adhoc(P); divide
14、 P into smaller subinstances P1,P2,Pk; for(i=1,i=k,i+) yi= divide-and-conquer(Pi); return merge(y1,y2,yk); ,|P|：问题P的规模； adhoc：分治法中的基本子运算 n0：阀值,如果问题P的规模不超过n0，说明问题已经容易求解，不要再继续分解。利用adhoc(P)直接求解。,分治法的设计模式,分治法的分割原则,分治法的分割原则 实践表明：将一个问题划分成大小相等的k个子问题的处理方法行之有效； 通常取k=2,分治法的计算效率分析,分治法的计算效率分析 通常用递归方程来进行分析 分治法将规
15、模为n的问题分成k个规模为n/m的子问题 设分解阈值n0=1，且adhoc解规模为1的问题耗费1个单位时间 设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题解需要使用f(n)个单位时间。 用T(n)表示该分治法divide-and-merge(P)解规模为|P|=n的问题所需要的计算时间,分治法的适用条件,分治法所能解决的问题一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包
16、含公共的子问题。,因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。,这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用,能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。,这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。,二分搜索技术 大整数的乘法 Strassen矩阵乘法 棋盘覆盖 合并排序 快速排序 线性时间选择 最近点对问题 循环赛日程表,二分搜索技术,分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的
