[工学]递归算法分析.pptVIP

递归关系常用于对递归函数的代价建模。例如，标准归并排序对一个长度为n的线性表进行处理，它的代价建模为： T(n)=2T(n/2)+n 三种常见的处理递归关系的方法： 估计法：猜测递归的上下限，然后根据需要进行收紧上下限。 扩展递归，把它转换成求和，然后利用求和技术。 当递归是某种特定形式时，利用已经证明的定理。 估计上下限 基本步骤：(1)猜测 (2)用数学归纳法证明. 关键：猜测 具体操作：如果给出一个正确的上下限估计，经过归纳证明很容易就可以验证事实。如果证明成功，那么就试着收紧上下限，如果证明失败，那么就放松限制再试着证明。一旦上下限符合要求，就完成了任务。 应用范围：当只是寻找渐进复杂性时，这是一种很有用的技术。当寻找一种精确的闭合形式解时（即寻找表达式的常量时），这个方法就不合适了。 估计上下限 例1. 求解, T(2)=1. 解： 可以从猜测这个递归有一个上限O(n2)开始，假定：T(n)=n2 归纳证明这个猜测是正确的: 假设n是2的乘方。 对于初始T(2)=1=22 假设T(i)=i2 i=n 则：T(2i)=2T(i)+i=2i2+2i=4i2=(2i)2 这样T(n)就在O(n2)中了 估计上下限 从上述证明过程中可以看到，我们从2n2+2n到达了4n2,表明O(n2)是一个很高的估计。 猜测更小些，例如T(n)=cn,很明显这样不行，因为c2n=2cn.所以真正的代价一定在cn与n^2之间。 估计上下限 猜测T(n)=nlogn 证明： T(2)=1 =2log2=2 假设T(n)=nlogn T(2n)=2T(n)+2n=2nlogn+2n=2n(logn+1)=2nlog2n 所以：T(n)在O(nlogn) 同样可以证明T(n)在Ω（nlogn）中， 因此T(n)也是θ(nlogn) 扩展递归关系 如果要找到精确的答案，就需要精确的技术，扩展递归就是其中一种技术。 例一：T(n)=T(n-1)+1 (n1) T(0)=T(1)=0 展开递归： T(n)=T(n-2)+2 T(n)=T(n-3)+3 ……………. T(n)=T(1)+n-1=n-1 然后用归纳法证明这个式子是正确的 扩展递归关系 例二：T(n)=T(n-1)+n T(1)=1 展开递归： T(n)=T(n-1)+n =T(n-2)+(n-1)+n =T(n-3)+(n-2)+(n-1)+n =1+2+….+n =n(n+1)/2 扩展递归关系 例三：T(n)=2T(n/2)+5n2 T(1)=7 为简单起见，假定n是2的乘方，我们把它重新写成n=2^k.递归关系可以像下面这样扩展： T(n)=2T(n/2)+5n2 =2(2T(n/4)+5(n/2)2)+5n2 =2(2(2(Tn/8)+5(n/4)2)+5(n/2)2)+5n2 =…….. =2kT(1)+2(k-1).5(n/2(k-1))2+….+2.5(n/2)2+5n2 扩展递归关系 扩展递归关系 结果为：7n+5n2(2-1/2(k-1)) = 7n+5n2(2-2/n) =7n+10n2-10n =10n2-3n 分治法递归 解决递归问题的第三种方法就是利用已经知道的定理，这些定理描述了一类递归问题的解。 例：一类已知的称为分治法递归的解的定理。这类问题具有形式： T(n)=aT(n/b)+cnk ; t(1)=c 归并排序，二分有哪些信誉好的足球投注网站都是分治法的例子 分治法递归 T(n)=aT(n/b)+cnk ; t(1)=c （1）使用扩展递归的方法为分治法递归推导出一般形式的解 假定n=bm 分治法递归 （1）分析 设r= bk/a （一） 如果r1 分治法递归 分治法递归 分治法递归 分治法递归 举例： T(n)=3T(n/5)+8n2 a=3 b=5 c=8 k=2 Θ(n2) T(n)=2T(n/2) +n A=2 b=2 c=1 k=1 Θ(n log n) 快速排序平均情况分析 快速排序平均情况分析 简化递归关系式，得到： 求和移位消除累加项，把方程两边都乘以n，从nT(n+1)的公式中减去结果。 快速排序平均情况分析 快速排序平均情况分析 (n+1)T(n+1) - nT(n)=C(n+1)2-Cn2 + 2T(n) =C(2n+1)+2T(n) (n+1)T(n+1)=C(2n+1)+(n+2)T(n) T(n+1)=C(2n+1) / (n+1) +( (n+2) / (n+1) )T(n) 因为：C(2n+1) / (n+1)2C 快速排序平均情况分析 T(n+1)=C(2n+1) / (n+1)