算法设计与分析ch2算法分析的数学基础.ppt
第二章 算法分析的数学基础,DB-LAB(2003),2.1.1 同阶函数集合 2.1.2 低阶函数集合 2.1.3 高阶函数集合 2.1.4 严格低阶函数集合 2.1.5 严格高阶函数集合 函数阶的性质,2.1 计算复杂性函数的阶,DB-LAB(2003),同阶函数集合,定义2.1.1(同阶函数集合)(f(n)=g(n)|c1,c20,n0,nn0,c1f(n)g(n)c2f(n)称为与f(n)同阶的函数集合。,DB-LAB(2003),Example,DB-LAB(2003),例2 证明,证.如果存在c1、c2 0，n0使得当nn0时，c16n3c2 n2。于是，当nc2/6时，n c2/6，矛盾。,Example,DB-LAB(2003),Example,DB-LAB(2003),2.1.2 低阶函数集合,DB-LAB(2003),Example,例 2 证明 n=O(n2).,DB-LAB(2003),高阶函数集合,DB-LAB(2003),DB-LAB(2003),严格低阶函数集合,DB-LAB(2003),DB-LAB(2003),DB-LAB(2003),严格高阶函数集合,DB-LAB(2003),Example,例 2.证明 n2/2 w(n2),DB-LAB(2003),DB-LAB(2003),函数阶的性质,DB-LAB(2003),2.1.6 函数阶的性质(续),DB-LAB(2003),注意,！,DB-LAB(2003),Flour 和 ceiling 多项式,2.2 标准符号和通用函数,DB-LAB(2003),Flour和ceiling,DB-LAB(2003),DB-LAB(2003),如果f(n)=O(nk),则称f(n)是多项式界限的。,DB-LAB(2003),1.线性和,2.3 和式的估计与界限,DB-LAB(2003),2.级数,DB-LAB(2003),DB-LAB(2003),3.和的界限,DB-LAB(2003),DB-LAB(2003),直接求和的界限,DB-LAB(2003),DB-LAB(2003),DB-LAB(2003),DB-LAB(2003),DB-LAB(2003),DB-LAB(2003),递归方程:递归方程是使用小的输入值来描述 一个函数的方程或不等式.,2.4 递归方程,递归方程例:Merge-sort排序算法的复杂性方程 T(n)=(1)if n=1 T(n)=2T(n/2)+(n)if n1.T(n)的解是(nlogn),DB-LAB(2003),Substitution方法:Guess first,然后用数学归纳法证明.Iteration方法:把方程转化为一个和式然后用估计和的方法来求解.Master方法:求解型为T(n)=aT(n/b)+f(n)的递归方程,求解递归方程的三个主要方法,DB-LAB(2003),Substitution方法：联想已知的T(n),例1.求解2T(n/2+17)+n,2.4.1 Substitution方法,证明：用数学归纳法,DB-LAB(2003),Substitution方法：猜测上下界，减少不确定性范围,DB-LAB(2003),细微差别的处理,问题：猜测正确，数学归纳法的归纳步 似乎证不出来 解决方法：从guess中减去一个低阶项，可能work.,DB-LAB(2003),DB-LAB(2003),避免陷阱,DB-LAB(2003),变量替换方法:经变量替换把递归方程变换为熟悉的方程.,DB-LAB(2003),方法：循环地展开递归方程，把递归方程转化为和式，然后可使用求和技术解之。,2.4.2 Iteration方法,DB-LAB(2003),DB-LAB(2003),2.4.3 Master method,DB-LAB(2003),Master 定理,DB-LAB(2003),对于红色部分，Master定理无能为力,DB-LAB(2003),DB-LAB(2003),Master定理的使用,DB-LAB(2003),Master定理的使用（续）,DB-LAB(2003),Master定理的证明,bi,DB-LAB(2003),Master定理的证明(续),DB-LAB(2003),引理2的证明,DB-LAB(2003),引理2的证明（续）,DB-LAB(2003),引理2的证明（续）,(f(n),DB-LAB(2003),Master定理的证明(续),DB-LAB(2003),引理3的证明,DB-LAB(2003),Master定理的证明(续),DB-LAB(2003),Master定理的证明(续),DB-LAB(2003),Master定理的证明(续),DB-LAB(2003),Master定理的证明(续),DB-LAB(2003),Master定理的证明(续),DB-LAB(2003),Master定理的证明(续),DB-LAB(2003),引理7的证明,DB-LAB(2003),引理7的证明,DB-LAB(2003),引理7的证明,
