算法设计与分析40学时课件ch2new

第二章 数学基础,骆吉洲 计算机科学与工程系,2.1 计算复杂性函数的阶 2.2 递归方程,提要,2.1.1 同阶函数集合 2.1.2 低阶函数集合 2.1.3 高阶函数集合 2.1.4 严格低阶函数集合 2.1.5 严格高阶函数集合 2.1.6 函数阶的性质,2.1 计算复杂性函数的阶,2.1.1 同阶函数集合,定义2.1.1 (同阶函数集合) (f(n)=g(n) | c1, c20, n0, nn0, c1f(n)g(n) c2f(n) 称为与f(n) 同阶的函数集合。,Example,例2 证明,证. 如果存在c1、c2 0，n0使得当nn0 时，c16n3c2 n2 。于是，当nc2 /6时， n c2 /6，矛盾。,Example,Example,2.1.2 低阶函数集合,Example,例 2 证明 n=O(n2).,2.1.3 高阶函数集合,2.1.4 严格低阶函数集合,2.1.5 严格高阶函数集合,Example,例 2. 证明 n2/2 w(n2),2.1.6 函数阶的性质,2.1.6 函数阶的性质(续),注意,！,递归方程: 递归方程是使用小的输入值来描述 一个函数的方程或不等式.,2.2 递归方程,递归方程例: Merge-sort排序算法的复杂性方程 T(n)=(1) if n=1 T(n)=2T(n/2)+(n) if n1. T(n)的解是(nlogn),迭代方法: 把方程转化为一个和式 然后用估计和的方法来求解. 替换方法: 先猜测方程的解, 然后用数学归纳法证明. Master方法: 求解型为T(n)=aT(n/b)+f(n)的递归方程,求解递归方程的三个主要方法,方法： 循环地展开递归方程， 把递归方程转化为和式， 然后可使用求和技术解之,2.2.1 迭代方法,© DB-LAB (2003),例2.T(n)=2T(n/2)+cn,=22T(n/22)+cn+cn,=23T(n/23)+cn+cn+cn =,=2kT(n/2k)+knc,=2kT(1)+knc n=2k,=nT(1)+cn log n =(nlogn),方法： 1.变量代换,将方程转换成已知方程 2.先根据方程的形式猜测解 然后用数学归纳法证明,2.2.2 替换法,例1.T(n)=2T(n/2+17)+n,变量代换,令n=m+34,则,S(m)=2S(m/2)+m+34,令T(m+34)=S(m),则,T(m+34)=2T(m/2+34)+m+34,S(m)=(mlogm),T(n)=(nlogn),例2.T(n)=2T(n1/2)+logn,令n=2m,则,S(m)=2S(m/2)+m,令T(2m)=S(m),则,T(2m)=2T(2m/2)+m,S(m)=(mlogm),T(n)=(logn loglogn),例1.T(n)=2T(n/2+17)+n,先猜后证,令n=m+34,则,S(m)=2S(m/2)+m+34,令T(m+34)=S(m),则,T(m+34)=2T(m/2+34)+m+34,S(m)=(mlogm),T(n)=(nlogn),猜测方法： 猜测上下界，减少不确定性范围,细微差别的处理,问题：猜测正确，数学归纳法的归纳步 似乎证不出来 解决方法:从猜测结论中减去一个低阶项， 可能方法就能用了,© DB-LAB (2003),避免陷阱,2.2.3 Master method,Master 定理,C1,对于红色部分，Master定理无能为力,Master定理的使用,Master定理的使用（续）,