《算法设计与分析递归式精.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析递归式精.ppt（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法设计与分析递归式算法设计与分析递归式第1页，本讲稿共25页第四章第四章 递归式递归式n4.1 4.1 假设归纳法假设归纳法n4.2 4.2 迭代方法迭代方法n4.3 4.3 主方法主方法第2页，本讲稿共25页概念及求解方法概念及求解方法n概念：概念：T(n)=f(T(g(n)(T(n)=f(T(g(n)(一般一般g(n)n)g(n)n)n三种求解方法三种求解方法n假设归纳法假设归纳法n迭代方法迭代方法n主方法主方法n求解方式求解方式 忽略细节忽略细节n假定式中假定式中n n为整数（略去底、顶函数）为整数（略去底、顶函数）n假定对小的假定对小的n n值值T(n)T(n)为常量（略去边界条件）
2、为常量（略去边界条件）n求解后再检查这些忽略的细节是否会影响结果求解后再检查这些忽略的细节是否会影响结果第3页，本讲稿共25页4.1 4.1 假设归纳法假设归纳法n先猜测解的形式，再用归纳法证明。先猜测解的形式，再用归纳法证明。n猜测技巧：猜测技巧：n类比猜测类比猜测如：如：T(n)=2T(T(n)=2T(n/2n/2 +17)+n+17)+nn逐步求精猜测逐步求精猜测O(1)O(lg n)O(n)O(n lg n)O(n2)0c0的常数，满足的常数，满足T(n)cn lg n T(n)cn lg n。证明：设对证明：设对 n/2n/2 满足，则满足，则T(n)2(c T(n)2(c n/2n
3、/2 1g(1g(n/2n/2 )+n )+n cn lg(n/2)+n cn lg(n/2)+n=cn lg n-cn lg 2+n=cn lg n-cn lg 2+n=cn lg n-cn+n=cn lg n-cn+n cn lg n,cn lg n,只需只需c 1c 1 即可。但该解对边界条件即可。但该解对边界条件T(1)=1T(1)=1不成立，但可选不成立，但可选n n0 0=2=2第5页，本讲稿共25页4.1 4.1 假设归纳法假设归纳法n归纳法证明时的技巧（续）：归纳法证明时的技巧（续）：n解中减一个低阶项（做一个更强的假设）。解中减一个低阶项（做一个更强的假设）。例：求例：求T(
4、n)=T(T(n)=T(n/2n/2 )+T()+T(n/2n/2 )+1)+1的界的界 猜测为猜测为O(n)O(n)，即证明存在，即证明存在c0c0的常数，满足的常数，满足T(n)cnT(n)cn。证明：设对证明：设对 n/2n/2 满足，则满足，则T(n)c T(n)c n/2n/2 +c +c n/2 n/2 +1 +1=cn+1=cn+1 得不到满足条件的得不到满足条件的c c。但猜测为但猜测为T(n)cn T(n)cn b b，有，有T(n)(c T(n)(c n/2n/2 -b)+(c -b)+(c n/2 n/2 -b)+1 -b)+1=cn-2b+1=cn-2b+1 cn-b
5、(cn-b (只要只要b1)b1)对小的值作更强的假设，可证明给定值更强的结论第6页，本讲稿共25页4.1 4.1 假设归纳法假设归纳法n归纳法证明时的技巧（续）：归纳法证明时的技巧（续）：n变量代换。变量代换。例：例：变量代换：变量代换：m=1g n m=1g n，得：，得：T(2T(2mm)=2T(2)=2T(2m/2m/2)+m)+m 再次变量代换：再次变量代换：S(m)=T(2S(m)=T(2mm)，得：，得：S(m)=2S(m/2)+mS(m)=2S(m/2)+m 则得则得S(m)=O(m lg m)S(m)=O(m lg m)得：得：T(n)=T(2T(n)=T(2mm)=S(m)
6、=O(m lg m)=O(lg n lg lg n).)=S(m)=O(m lg m)=O(lg n lg lg n).第7页，本讲稿共25页4.1 4.1 假设归纳法假设归纳法n避免陷阱：避免陷阱：例：例：T(n)2(c T(n)2(c n/2n/2 )+n )+n cn+n cn+n=O(n)-=O(n)-错误错误此处未证明归纳假设的准确形式：此处未证明归纳假设的准确形式：T(n)cn T(n)cn第8页，本讲稿共25页4.2 4.2 迭代方法迭代方法n扩展递归式，然后进行和式求解扩展递归式，然后进行和式求解(计算复杂计算复杂)。例：例：T(n)=3T(T(n)=3T(n/4n/4 )+n
7、.)+n.T(n)=n+3T(T(n)=n+3T(n/4n/4 )=n+3(=n+3(n/4n/4 +3T(+3T(n/16n/16 )=n+3(=n+3(n/4n/4 +3(+3(n/16n/16 +3T(+3T(n/64n/64 )=n+3=n+3 n/4n/4 +9 +9 n/16n/16 +27T(+27T(n/64n/64 )当当 n/4n/4i i =1=1即即i i超过超过loglog4 4n n时，扩展达到时，扩展达到边界边界。故：。故：第9页，本讲稿共25页4.2 4.2 迭代方法迭代方法n要点：要点：n什么时候达到边界什么时候达到边界;n迭代过程的每一层中各项的和迭代过程的
8、每一层中各项的和;n若迭代过程中已能估计出界的形式，则可以若迭代过程中已能估计出界的形式，则可以改用假设归纳法。改用假设归纳法。第10页，本讲稿共25页4.2 4.2 迭代方法迭代方法n图解法图解法 递归树：递归树：例：例：T(n)=2T(n/2)+nT(n)=2T(n/2)+n2 2第11页，本讲稿共25页4.2 4.2 迭代方法迭代方法n图解法图解法 递归树：递归树：例：例：T(n)=2T(n/2)+nT(n)=2T(n/2)+n2 2（续）（续）第12页，本讲稿共25页4.2 4.2 迭代方法迭代方法n图解法图解法 递归树：递归树：例例2 2：T(n)=T(n/3)+T(2n/3)+nT
9、(n)=T(n/3)+T(2n/3)+n第13页，本讲稿共25页4.3 4.3 主方法主方法n用于解如下形式的递归式：用于解如下形式的递归式：T(n)=aT(n/b)+f(n)T(n)=aT(n/b)+f(n)其中其中a1a1，b1b1是常数，是常数，f(n)f(n)是一个渐近是一个渐近正函数。正函数。（式中使用顶、底函数并不影响结果）（式中使用顶、底函数并不影响结果）第14页，本讲稿共25页4.3 4.3 主方法主方法n主定理：主定理：设设a1a1和和b1b1是常数，是常数，f(n)f(n)为一函数，为一函数，T(n)T(n)是由下面是由下面的递归式定义：的递归式定义：T(n)=aT(n/b
10、)+f(n)(n/b T(n)=aT(n/b)+f(n)(n/b指指 n/bn/b 或或 n/bn/b )。则则T(n)T(n)可有如下渐近界：可有如下渐近界：1.1.若对某常数若对某常数 00，有，有f(n)=f(n)=，则有，则有T(n)=T(n)=；2.2.若若f(n)=f(n)=，则，则T(n)=T(n)=；3.3.若对某常量，有若对某常量，有f(n)=f(n)=，且对常量，且对常量c1c1与足够大与足够大的的n n，有，有af(n/b)af(n/b)cf(n)cf(n)，则，则T(n)=T(n)=(f(n)(f(n)。第15页，本讲稿共25页4.3 4.3 主方法主方法n主定理解读主
11、定理解读第16页，本讲稿共25页4.3 4.3 主方法主方法n主定理解读（续）：主定理解读（续）：界由界由f(n)f(n)和和 中大的那个决定；中大的那个决定；n第一种情况为：第一种情况为：f(n)f(n)多项式小于多项式小于 时，时，解为解为n第三种情况为：第三种情况为：f(n)f(n)多项式大于多项式大于 ，并，并满足条件满足条件af(n/b)af(n/b)cf(n)cf(n)时，解为时，解为(f(n)(f(n)n第二种情况为：两者渐近相等时，解为第二种情况为：两者渐近相等时，解为第17页，本讲稿共25页4.3 4.3 主方法主方法n主定理应用：主定理应用：例例1 1：T(n)=9T(n/
12、3)+n T(n)=9T(n/3)+n 其中其中a=9a=9，b=3b=3，f(n)=nf(n)=n，则，则因为因为f(n)=f(n)=，其中，其中=1=1。这对应于主定理的第一种情。这对应于主定理的第一种情况，故解为：况，故解为：T(n)=T(n)=(n(n2 2)例例2 2：T(n)=T(2n/3)+1 T(n)=T(2n/3)+1 其中其中a=1a=1，b=3/2b=3/2，f(n)=1f(n)=1，则，则即满足第二种情况，故解为：即满足第二种情况，故解为：T(n)=T(n)=(lg n)(lg n)第18页，本讲稿共25页4.3 4.3 主方法主方法n主定理应用主定理应用(续续)：例例
13、3 3：T(n)=3T(n/4)+n lg n T(n)=3T(n/4)+n lg n 其中其中a=3a=3，b=4b=4，f(n)=n lg nf(n)=n lg n，则，则因为因为f(n)=f(n)=，其中，其中 0.20.2。若证明条件。若证明条件af(n/b)af(n/b)cf(n)cf(n)，则该问题对应于主定理的第三种情况。对足够大，则该问题对应于主定理的第三种情况。对足够大的的n n，af(n/b)=3(n/4)lg(n/4)af(n/b)=3(n/4)lg(n/4)(3/4)n lg n=cf(n)(3/4)n lg n=cf(n)，即，即c=3/4c=3/4。故解为：。故解为
14、：T(n)=T(n)=(n lg n)(n lg n)例例4 4：T(n)=2T(n/2)+n 1g n T(n)=2T(n/2)+n 1g n 其中其中a=2a=2，b=2b=2，f(n)=n 1g n f(n)=n 1g n，看似满足第三种情况，但看似满足第三种情况，但 f(n)=n 1g n f(n)=n 1g n渐近大于渐近大于 ，不，不是多项式大于是多项式大于 (对任意正常数对任意正常数，比值，比值=(n lg n)/n=lg n=(n lg n)/n=lg n渐近小于渐近小于n n)第19页，本讲稿共25页4.3 4.3 主方法主方法n主定理证明主定理证明第20页，本讲稿共25页4
15、.3 4.3 主方法主方法n主定理证明（情况一）主定理证明（情况一）f(n)=f(n)=，有，有 则：则：第21页，本讲稿共25页4.3 4.3 主方法主方法n主定理证明（情况二）主定理证明（情况二）f(n)=f(n)=，有，有 则：则：第22页，本讲稿共25页4.3 4.3 主方法主方法n主定理证明（情况三）主定理证明（情况三）af(n/b)af(n/b)cf(n)cf(n)，有，有a aj jf(n/bf(n/bj j)c cj jf(n)f(n)，则：则：第23页，本讲稿共25页作业作业n1.1.用归纳法证明用归纳法证明T(n)=2T(T(n)=2T(n/2n/2 )+n)+n的解为的解为(n lg n)(n lg n)n2.2.用主方法证明，二分查找法用主方法证明，二分查找法T(n)=T(n/2)+T(n)=T(n/2)+(1)(1)的解为的解为T(n)=T(n)=(lg n)(lg n)第24页，本讲稿共25页The EndThe EndnThank you!Thank you!第25页，本讲稿共25页