算法设计与分析ch2

《算法设计与分析ch2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章算法分析的数学基础骆吉洲计算机科学与工程系参考资料《IntroductiontoAlgorithms》第三章第四章《网站资料》第二章©DB-LAB(2003)2.1计算复杂性函数的阶2.2标准符号和通用函数2.3和式的估计与界限2.4递归方程提要©DB-LAB(2003)2.1.1同阶函数集合2.1.2低阶函数集合2.1.3高阶函数集合2.1.4严格低阶函数集合2.1.5严格高阶函数集合2.1.6函数阶的性质2.1计算复杂性函数的阶©DB-LAB(2003)2.1.1同阶函数集合定义2.1.1(同阶函数集合)(f(n))={g(n)

2、c1,c2>0,

3、n0,n>n0,c1f(n)g(n)c2f(n)}称为与f(n)同阶的函数集合。©DB-LAB(2003)Example©DB-LAB(2003)例2证明证.如果存在c1、c2>0，n0使得当nn0时，c1n26n3c2n2。于是，当n>c2/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)2.1.3高阶函数集合©DB-LAB(2003)©DB-LAB(2003)2.1.4严格低阶

4、函数集合©DB-LAB(2003)©DB-LAB(2003)©DB-LAB(2003)2.1.5严格高阶函数集合©DB-LAB(2003)Example例2.证明n2/2w(n2)©DB-LAB(2003)©DB-LAB(2003)2.1.6函数阶的性质©DB-LAB(2003)2.1.6函数阶的性质(续)©DB-LAB(2003)注意！©DB-LAB(2003)Flour和ceiling多项式2.2标准符号和通用函数©DB-LAB(2003)2.2.1Flour和ceiling©DB-LAB(2003)©DB-LAB(2003)如果f(n)=O(nk),则

5、称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)ifn=1T(

6、n)=2T(n/2)+(n)ifn>1.T(n)的解是(nlogn)©DB-LAB(2003)Substitution方法:Guessfirst,然后用数学归纳法证明.Iteration方法:把方程转化为一个和式然后用估计和的方法来求解.Master方法:求解型为T(n)=aT(n/b)+f(n)的递归方程求解递归方程的三个主要方法©DB-LAB(2003)Substitution方法Ⅰ：联想已知的T(n)例1.求解2T(n/2+17)+n2.4.1Substitution方法证明：用数学归纳法©DB-LAB(2003)Substitution方法Ⅰ：猜测

7、上下界，减少不确定性范围©DB-LAB(2003)细微差别的处理问题：猜测正确，数学归纳法的归纳步似乎证不出来解决方法：从guess中减去一个低阶项，可能work.©DB-LAB(2003)©DB-LAB(2003)避免陷阱©DB-LAB(2003)变量替换方法:经变量替换把递归方程变换为熟悉的方程.©DB-LAB(2003)方法：循环地展开递归方程，把递归方程转化为和式，然后可使用求和技术解之。2.4.2Iteration方法©DB-LAB(2003)©DB-LAB(2003)2.4.3Mastermethod©DB-LAB(2003)Master定理©DB

8、-LAB(2003)T(n)=(nlogba)T(n)=(f(n))f(n)(f(n)lgn)nn-对于红色部分，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定

9、理的证明(续)©DB-LAB(2003