学习]算法设计与分析王佳02递归.ppt

《学习]算法设计与分析王佳02递归.ppt》由会员分享，可在线阅读，更多相关《学习]算法设计与分析王佳02递归.ppt（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、主讲教师 王佳信息学院界限与递归floor和ceiling 一、界限和式的估计与界限 1.线性和 2.级数 3.和的界限直接求和的界限 二、递归与递归式2.1 递归与递归程序设计1.什么是递归？递归是一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法。1）递归的本质递归把一个大型、复杂的问题层层转化为一个与原问题相似、但规模较小的问题来求解，只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。2）递归的结构一般来说，递归由边界条件、递归计算和递归返回组成。当边界条件不满足时，递归向前推进计算过程；当边界条件满

2、足时，递归返回。2.递归程序设计程序调用自身的编程技术称为递归程序设计。是递归算法的直接描述。关于递归，注意两点：(1)递归就是在过程或函数里直接或简接地调用自身;(2)在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口，否则会产生死循环而出错。例2.1 斐波那契(Fibonacci)序列：F0=F1=1 Fi=Fi-1+Fi-2（i1)算法2.1 求斐波那契数：procedure F(n)/返回第n个斐波那契数/integer n if n 1 then return(1)else return(F(n-1)+F(n-2)endif end F思考：上述算法的效率非常低下，为什么？

3、上述过程的效率很差，存在大量的重复计算：改进：保存中间结果（递推模型）其它递归模型F(n)F(n-1)F(n-2)F(n-2)F(n-3)F(n-3)F(n-4)分析：F(n-2)被算了两次，F(n-3)被算了三次，F(n-4)被算了五次，.，总的运算量为这些运算之和，所以，事实上，这样的计算过程，运算次数本身也是一个斐波那契数列。整个计算的时间复杂度约为O(1.618n)。非常之大！例2.2 欧几里得算法已知两个非负整数a和b，且ab0，求这两个数的最大公因数。辗转相除法：若b=0，则a和b的最大公因数等于a；若b0，则a和b的最大公因数等于b和用b除a的余数的最大公因数。算法2.2 求最大

4、公因数procedure GCD(a,b)/约定ab/if b=0 then return(a)else return(GCD(b,a mod b)endif end GCD 例：GCD(22,8)=GCD(8,6)=GCD(6,2)=GCD(2,0)=2例2.3 用递归策略设计的检索算法已知元素x和元素表A（1：n），判断x是否等于A中某元素的值。算法2.3 在A（1：n）中检索x procedure SEARCH(i)/如果在A（1：n）中有一元素A(k)=x，则将其第一次出现的下标k返回，否则返回0/global n,x,A(1:n)case :in:return(0):A(i)=x;r

5、eturn(i):else:return(SEARCH(i+1)endcase end SEARCH递归是一种强有力的设计方法与数学模型一致表述简单、清晰、代码量少可读性强、容易证明正确性递归的问题：执行时间长、运行效率低，特别是占用空间多，容易造成系统栈的溢出。主要原因：递归调用时有大量的现场保护与恢复操作，需要时间处理；在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储，递归层次数过多容易造成栈溢出等。3.怎么克服递归的效率问题？化递归为递推递归：递归是一种从上至下的“分解求解“的过程，即不断地把大问题分解为小问题，直到小问题规模足够小，然后求解并进行递归返回和结果合并。效率

6、差！递推：递推是一种从下往上的“合并求解“过程，即从解决小问题出发，记录小问题的答案，并根据已有的小问题的答案，把问题往大里扩展，“滚雪球”，直到达到大问题的规模为止。并通常用迭代（循环）的方式实现，而不是递归调用，一般认为效率上比递归好。递归和递推的联系：都存在重复计算，是解决较大规模问题的有效方法；递归和递推的区别：求解思路不同，实现技术上也不一样递归算法设计的思想Recursive_SOLVE(P)/P是当前问题 if P的规模足够小 then 直接求解 else 将P转换为规模较小问题P Recursive_SOLVE(P)/递归调用 将P还原成为原问题P，结果合并 endifEND

7、Recursive_SOLVE 递推算法设计的思想 Recurrence_SOLVE(P)/P是当前问题 定义数组ansP /定义一个与问题规模P相适应的数组，用于存放答案 for i from 边界问题P0 to P do /从小问题求解做起 if i 是边界值then 直接求解，将结果保存在ans中 else 将i转换为规模较小问题iansi build answer by ansi /用已得到的答案构造i的解ansi endif repeatEND Recurrence_SOLVE化递归为递推的基本策略：u调用递归函数与调用其它函数没有本质的区别，就是调用一个函数而已，只不过这个函数的名

8、称是自己。u理解程序中调用函数的原理。u用用户自定义栈、断点、基于标号的程序转向实现程序的重复执行、断点返回、返回函数值等实际上是人工模拟原来由编译程序自动编制执行过程的行为。在函数调用之前，系统需完成三件事：为被调用过程的局部变量分配存储区；将所有的实参、返回地址等信息传递给被调用过程保存；将控制转移到被调过程的入口。从被调用过程返回调用过程之前，系统也应完成三件工作：保存被调过程的计算结果；释放被调过程的数据区；依照被调过程保存的返回地址将控制转移到调用过程。函数调用原理化递归为递推的具体方法十三条规则，可以把直接递归过程转化为与之等价的迭代过程。具体见计算机算法基础3.2节余祥宣崔国华邹

9、海明出版社：华中科技大学出版社2.2 递归式及其求解1.递归式递归式是一组等式或不等式，它所描述的函数是用在更小的输入下该函数的值来定义的。递归算法（或具有递归性质的迭代算法）的运行时间通常用递归式表示。如：归并排序（MERGESORT）的运行时间T(n)表示如下：T(n)=(1)if n=1 T(n)=2T(n/2)+(n)if n1.T(n)的解是(nlogn)递归式和递推式1)递推式Recurrence数列：按一定次序排列的一列数称为数列（sequence of number）。数列中的每一个数都叫做这个数列的项。排在第一位的数称为这个数列的第1项，排在第二位的数称为这个数列的第2项排在

10、第n位的数称为这个数列的第n项，数列的一般形式可以写成a1，a2，a3，an，简记为an。递推公式：通过给出数列的第1项（或前若干项），并给出数列的某一项与它的前一项（或前若干项）的关系式来表示数列，这种表示数列构造方式的式子叫做这个数列的递推公式。递推公式是数列所特有的表示法，它包含两个部分：（1）初始条件边界值；（2）递推关系an与其他一项或多项之间的构造规律。二者缺一不可。例如：斐波纳契数列的递推公式为fn=fn-1+fn-2 等差数列递推公式：an=an-1+d 等比数列递推公式：bn=bn-1q2)递归式Recursion递归公式：当递推式中只含数列中的项，而无常数项或其它项时，就叫

11、做递归公式。所以，递归公式属于递推公式的一个特例。例如，自然数列用通项公式表示为：an=n 用递推公式表示为：an+1=an+1 初始条件：a1=1 用递归公式表示为：an+2=2an+1-an，初始条件：a1=1，a2=2 这里，没有过于细致地区分递归式与递推式，我们视为一致。2.递归式的求解这里所说的求解递归式就是化简递归式，以得到形式简单的限界函数表示（即O、的表示）。三种常用方法：代换（Substitution）方法:Guess first,然后用数学归纳法证明.迭代（Iteration）方法:把方程转化为一个和式然后用估计和的方法来求解.主（Master）方法:求解型为T(n)=aT

12、(n/b)+f(n)的递归方程 对表达式细节的简化为便于处理，通常做如下假设和简化处理(1)运行时间函数T(n)的定义中，一般假定自变量为整数。(2)忽略递归式的边界条件，即n较小时函数值的表示。原因在于，虽然递归式的解会随着T(1)值的改变而改变，但此改变不会超过常数因子，对函数的阶没有根本影响。(3)对上取整、下取整运算做合理简化，如通常忽略上、下取整函数，直接写作：注：被简化的细节并不是不重要，只是这些细节处理不影响算法分析的渐近界，是“无限大”分析中的合理假设和简化。在细节被简化处理的同时，也要知道它们在什么情况下是“实际”重要的。这样就可以了解算法在各种情况的具体执行情况。1)代换法

13、用代换法解递归式基本思想：先猜测一个界，然后用数学归纳法证明该猜测的正确性，亦即，用该猜测作为归纳假设，在推论证明时作为较小值代替函数的解，然后证明推论的正确性。用代换法解递归式的步骤：(1)猜测渐近界的形式(2)用数学归纳法证明猜测的正确性例：用代换法确定下式的上界分析：该式与类似，故猜测其解为O(nlogn)。现在想法证明T(n)cnlogn，并确定常数c的存在。假设该界对成立，即 ，然后在数学归纳法推论证明阶段对递归式做替换，有：故，要使T(n)cnlogn成立，只要c1就可以，这样的c是存在的、合理的。上面的证明过程，证明了当n足够大时猜测的正确性。但边界值呢？即：T(n)cnlogn

14、的结论对于小n成立吗？分析：事实上，对n=1，上述结论存在问题：作为边界条件，我们有理由假设T(1)=1，但对n=1，T(1)c1log1=0，与T(1)=1不相符。也即，T(n)cnlogn对于归纳证明的基本情况不成立。怎么处理？从O的定义出发：只需要存在常数n0，使得nn0时结论成立即可n0不一定取1。所以，这里，我们不取n0=1，而取n0=2，并将T(2)、T(3)作为归纳证明中的边界条件代替T(1)（但依旧假设T(1)=1）使得T(2)、T(3)满足T(n)cnlogn。而n3时，递归计算不再直接依赖T(1)，使用T(2)、T(3)即可完成。带入T(1)=1，通过递归式有，T(2)=4

15、，T(3)=5，如何使T(2)、T(3)满足T(n)cnlogn？只要c取足够大的常数使得T(2)c2log2和T(3)c3log3成立即可。这样的c是什么？答案：只要c2即可。综上所述，取常数c2，最终的结论T(n)cnlogn就成立。命题得证。如何猜测递归式的渐近界呢？1）主要靠经验u尝试1：看有没有形式上类似的表达式，以此推测新递归式的渐近界。u尝试2：先猜测一个较宽的界，然后再缩小不确定区间，收缩到精确的渐近界。2）避免盲目推测如：原因：没有证明一般形式T(n)cn。从T(n)=cn+n不可能得到T(n)0,我们都得不到cn+n1；f(n)是一个渐近正的函数。含义：规模为n的原问题被分

16、为a个子问题，每个子问题的规模是n/b，a和b是正常数。子问题被递归地求解，T(n)是原始问题的时间，每个子问题的时间为T(n/b)；划分出来的子问题的答案合并及其它有关运算的代价由函数f(n)描述。上式给出了算法总代价与子问题代价的关系。注：这里采用了细节的简化，没有考虑n/b的取整问题，省略了下取整、上取整，但本质上不影响对递归式渐近行为的分析。对上述形式的递归式渐近界的求解是依赖称之为“主定理”的结论给出的。Master 定理 理解主定理：1）T(n)的解似乎与f(n)和有“密切关联”：f(n)和比较，T(n)取了其中较大的一个。如：第一种情况，函数比较大，所以第三种情况，函数f(n)比

17、较大，所以第二种情况，两个函数一样大，则乘以对数因子，得2)在第一种情况中，f(n)要多项式地小于。即，对某个常量0，f(n)必须渐近地小于，两者相差了一个 因子。3)在第三种情况中，f(n)不仅要大于，而且要多项式地大于，还要满足一个“规则性”条件。4)若递归式中的f(n)与的关系不满足上述性质：u f(n)小于，但不是多项式地小于u f(n)大于，但不是多项式地大于或不满足规则条件则不能用主方法求解该递归式。使用主方法：分析递归式满足主定理的哪种情形，然后直接写出相应的答案，而无需证明。例2.6 解递归式分析：这里，a=9，b=3，f(n)=n。则。因为，其中=1，所以对应主定理的第一种情况，于是有例2.7 解递归式分析：这里，a=1，b=3/2，f(n)=1，主定理第二种情况成立 因为，故T(n)=(logn)例2.8 解递归式分析：这里，a=3，b=4，f(n)=nlogn，故，成立，其中0.2。同时，对足够大的n，其中c=3/4。所以第三种情况成立，T(n)=(nlogn)。例2.9 递归式不能用主方法求解分析：这里，a=2，b=2，且，f(n)=nlogn 渐进大于第三种情况成立吗？事实上不成立，不满足 这里要求,f(n)多项式地大于 因此该递归式落在情况二和情况三之间，条件不成立，不能用主定理求解。注：在使用主定理时不用证明其正确性。