算法设计与分析4递归式

1、算法设计与分析2007.91第四章 递归式4.1 假设归纳法4.2 迭代方法4.3 主方法2概念及求解方法概念：T(n)=f(T(g(n) (一般g(n) n)三种求解方法假设归纳法迭代方法主方法求解方式 忽略细节假定式中n为整数（略去底、顶函数）假定对小的n值T(n)为常量（略去边界条件）求解后再检查这些忽略的细节是否会影响结果34.1 假设归纳法先猜测解的形式，再用归纳法证明。猜测技巧：类比猜测如：T(n) = 2T(n/2 + 17) + n逐步求精猜测O(1)O(lg n)O(n)O(n lg n)O(n2)0的常数，满足T(n) cn lg n 。 证明：设对n/2 满足，则T(n)

2、 2(c n/2 1g ( n/2 ) + n cn lg(n/2) + n = cn lg n - cn lg 2 + n = cn lg n - cn + n cn lg n, 只需c 1 即可。但该解对边界条件T(1)=1不成立，但可选n0=254.1 假设归纳法归纳法证明时的技巧（续）：解中减一个低阶项（做一个更强的假设）。例：求T(n) = T( n/2 ) + T ( n/2 ) + 1的界 猜测为O(n)，即证明存在c0的常数，满足T(n) cn。 证明：设对n/2 满足，则T(n) c n/2 + c n/2 + 1 = cn + 1 得不到满足条件的c。但猜测为T(n) cn

3、 b，有T(n) (c n/2 - b) + (c n/2 - b) + 1 = cn - 2b + 1 cn - b (只要b1)对小的值作更强的假设，可证明给定值更强的结论64.1 假设归纳法归纳法证明时的技巧（续）：变量代换。例： 变量代换：m = 1g n ，得：T(2m) = 2T(2m/2) + m 再次变量代换：S(m) = T(2m) ，得：S(m) = 2S(m/2) + m 则得S(m)=O(m lg m) 得：T(n)=T(2m)=S(m)=O(m lg m)=O(lg n lg lg n). 74.1 假设归纳法避免陷阱：例：T(n) 2(c n/2 ) + n cn

4、+ n = O(n) - 错误此处未证明归纳假设的准确形式： T(n) cn84.2 迭代方法扩展递归式，然后进行和式求解(计算复杂)。例：T(n) = 3T(n/4 ) + n. T(n) = n + 3T(n/4 ) = n + 3 (n/4 + 3T(n/16 ) = n + 3(n/4 + 3(n/16 + 3T(n/64 ) = n + 3 n/4 + 9 n/16 + 27T(n/64 )当n/4i =1即i超过log4n时，扩展达到边界。故：94.2 迭代方法要点：什么时候达到边界;迭代过程的每一层中各项的和;若迭代过程中已能估计出界的形式，则可以改用假设归纳法。104.2 迭代

5、方法图解法 递归树：例：T(n)=2T(n/2)+n2114.2 迭代方法图解法 递归树：例：T(n)=2T(n/2)+n2 （续） 124.2 迭代方法图解法 递归树：例2：T(n)=T(n/3)+T(2n/3)+n134.3 主方法用于解如下形式的递归式：T(n)=aT(n/b)+f(n)其中a1，b1是常数，f(n)是一个渐近正函数。（式中使用顶、底函数并不影响结果）144.3 主方法主定理：设a1和b1是常数，f(n)为一函数， T(n)是由下面的递归式定义： T(n)=aT(n/b)+f(n) (n/b指n/b 或n/b )。则T(n)可有如下渐近界：若对某常数0，有f(n)= ，则

6、有T(n)= ；若f(n)= ，则T(n)= ；若对某常量，有f(n)= ，且对常量c1与足够大的n，有af(n/b) cf(n)，则T(n)=(f(n)。154.3 主方法主定理解读164.3 主方法主定理解读（续）：界由f(n)和 中大的那个决定；第一种情况为：f(n)多项式小于 时，解为第三种情况为：f(n)多项式大于 ，并满足条件af(n/b) cf(n)时，解为(f(n)第二种情况为：两者渐近相等时，解为174.3 主方法主定理应用：例1：T(n) = 9T(n/3) + n 其中a=9，b=3，f(n)=n，则因为f(n)= ，其中=1。这对应于主定理的第一种情况，故解为：T(n)

7、= (n2)例2：T(n) = T(2n/3) + 1 其中a=1，b=3/2，f(n)=1，则即满足第二种情况，故解为：T(n)= (lg n)184.3 主方法主定理应用(续)：例3：T(n) = 3T(n/4) + n lg n 其中a=3，b=4，f(n)=n lg n，则因为f(n)= ，其中0.2。若证明条件af(n/b) cf(n) ，则该问题对应于主定理的第三种情况。对足够大的n，af(n/b) = 3(n/4) lg(n/4) (3/4)n lg n = cf(n)，即c=3/4。故解为：T(n)= (n lg n)例4：T(n) = 2T(n/2) + n 1g n 其中a=2，b=2，f(n)= n 1g n ，看似满足第三种情况，但 f(n)= n 1g n渐近大于 ，不是多项式大于 (对任意正常数，比值=(n lg n) / n = lg n渐近小于n)194.3 主方法主定理证明204.3 主方法主定理证明（情况一）f(n)= ，有 则：214.3 主方法主定理证明（情况二）f(n)= ，有 则：224.3 主方法主定理证明（情况三）af(n/b) cf(n) ，有ajf(n/bj