算法导论第四章.doc

算法导论第四章 摘自：百度文库/link?url=QunHIQ6sgLN_uMads3Llc8mtkAKSkrn4OI9SuM_g3Tj_0a5N2fkRVV03F9-iiPOgdcm7zAj54KToWqfeFvNffHr-WaJpeqXzWkDRzewxuhm /tanky-woo/archive/2011/04/12/144020.html 这一章讲的是递归式(recurrence)，递归式是一组等式或不等式，它所描述的函数是用在更小的输入下该函数的值来定义的。 本章讲了三种方法来解递归式，分别是代换法，递归树方法，主方法。 1.代换法(Substitution method)(P38~P40) 定义：即在归纳假设时，用所猜测的值去代替函数的解。 用途：确定一个递归式的上界或下界。 缺点：只能用于解的形式很容易猜的情形。 总结：这种方法需要经验的积累，可以通过转换为先前见过的类似递归式来求解。 2.递归树方法(Recursion-tree method) 起因：代换法有时很难得到一个正确的好的猜测值。 用途：画出一个递归树是一种得到好猜测的直接方法。 分析(重点)：在递归树中，每一个结点都代表递归函数调用集合中一个子问题的代价。将递归树中每一层内的代价相加得到一个每层代价的集合，再将每层的代价相加得到递归式所有层次的总代价。 总结：递归树最适合用来产生好的猜测，然后用代换法加以验证。 递归树扩展过程：①.第二章2.3.2节分析分治法时图2-5(P21~P22)的构造递归树过程；②.第四章P41图4-1的递归树构造过程；这两个图需要好好分析。 3.主方法(Master method) 优点：针对形如T(n) = aT(n/b) + f(n)的递归式 缺点：并不能解所有形如上式的递归式的解。 具体分析： T(n) = aT(n/b) + f(n)描述了将规模为n的问题划分为a个子问题的算法的运行时间，每个子问题的规模为n/b。 在这里可以看到，分治法就相当于a=2, b=2, f(n) = O(n). 主方法依赖于主定理：(图片点击放大) 图片可以不清晰，可以看书。 主定理的三种情况，经过分析，可以发现都是把f(n)与 比较。 第一种情况是 更大，第二种情况是 与f(n)相等，第三种情况是f(n)更大。 但是，这三种情况并未完全覆盖所有可能的f(n)： 第一种情况是f(n)多项式的小于 ，而第三种情况是f(n)多项式的大于 ，即两者相差的是 。如果两者相差的不是 ，则无法用主定理来确定界。 比如算法导论P44最下面的 就不能用主定理来判断。 至于主定理的证明，有兴趣的可以拿笔在纸上推算，反正我这里是没看的，毕竟时间有限，要选择性的学习。