算法设计与分析资料报告讲义chapter2.doc

《算法设计与分析资料报告讲义chapter2.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章算法分析的数学基础outline1算法复杂性的阶2和式的估计与界限3递归方程4集合、关系、函数、图、树等5计数原理和概率论2.1复杂性函数的阶2.1.1同阶函数集合定义2.1.1(同阶函数集合).q(f(n))={g(n)

2、$c1,c2>0,n0,当n³n0,c1f(n)£g(n)£c2f(n)}称为与f(n)同阶的函数集合。*如果g(n)Îq(f(n)),我们称个g(n)与f(n)同阶。*g(n)Îq(f(n))常记作g(n)=q(f(n))。*f(n)必须是极限非负的，即当n充分大以后，f

3、(n)是非负的，否则=空集。例1证明证.设，令c1=a/4,c2=7a/4,则，令。当时成立。例2证明证.如果存在c1、c2>0，n0使得当n³n0时，c1£6n3£c2n2。于是，当n>c2/6时，n£c2/6，矛盾。例3例4因任何常数，，如果令。2.1.2低阶函数集合定义2.1.2(低阶函数集合).O(f(n))={g(n)

4、$c>0,n0,当n³n0,0£g(n)£cf(n)}称为比f(n)低阶的函数集合。*如果g(n)ÎO(f(n)),称f(n)是g(n)的上界。*g(n)ÎO(f(n))常

5、记作g(n)=O(f(n))。例1例2证明。证.令c=1,n0=1,则当时，。2.1.3高阶函数集合定义2.1.3(高阶函数集合).W(f(n))={g(n)

6、$c>0,n0,当n³n0,0£cf(n)£g(n)}称为比f(n)高阶的函数集合。*如果g(n)ÎW(f(n)),称f(n)是g(n)的下界。*g(n)ÎW(f(n))常记作g(n)=W(f(n))。定理2.1.对于任意f(n)和g(n),iff而且f(n)=W(g(n)).证.如果,则当时,.显然.如果且,则由可知，存在使得，当，。由f(

7、n)=W(g(n))可知，使得当，令,则当，。2.1.4.严格低阶函数集合定义2.1.4(严格低阶函数集合).forall}称为严格比g(n)低阶的函数集合。*如果f(n)Îo(g(n)),称g(n)是f(n)的严格上界。*f(n)Îo(g(n))常记作f(n)=o(g(n))。例1.证明证.对,欲，必，即。所以，当时，对，n³n0。例2．证明证.当c=1>0时，对于任何,当，都不成立命题2.1.证.由于f(n)=o(g(n)),对任意e>0,存在，当时,0£f(n)

8、.5严格高阶函数集合定义2.1.4(严格高阶函数集合).，forall称为严格比g(n)高阶的函数集合。命题2.2.f(n)Îw(g(n))iffg(n)Îo(f(n)).证：Þ对，1/c>0.由知,对1/c>0,,当时,(1/c)g(n)0,1/c>0.由可知,当时,g(n)<(1/c)f(n)，即cg(n)0,cn2c.令n0=2c+1,则当n³n0,

9、/2.例2.证明n2/2=w(n2).证.若n2/2=w(n2)，则对于c=1/2,存在n0,当时,2cg(n),即当n³n0时,f(n)/g(n)>c.于是,.2.1.6函数阶的性质A传递性：（a）（b）（c）（d）（e）.B自反性：（a），（b），（c）.C对称性.D反对称性：*并非所有函数都是可比的，即对于函数和，可能.例如,和.2.2标准符号和通用函数2.2.1Flour和ceiling定义2

10、.2.1(Flours和ceiling).表示小于或等于x的最大整数.表示大于等于x的最小整数.命题2.2.1命题2.2.2对于任意函数n,证.若,则，.于是若n=2k+1,则.命题2.2.3设n、a、b是任意整数，，则(1)。(2)证.(1)若,则。若，0<，则=(2)类似于(1)的证法。2.2.2多项式命题2.2.4,其中证.由于，，所以。定义2.2.2如果如果，则城是多项式界限的。2.3和2.3.1求和公式的性质1线性和命题2.4.5命题2.4.6证.对n用数学归纳法证明。当时，显然成立。假设

11、时成立。令，则。2.级数命题2.4.7命题2.4.8命题2.4.9n命题2.4.10.命题2.4.11命题2.4.12命题2.4.133和的界限·数学归纳法证明例1.证明证证明对于c³2/3,存在一个n0,当时.当n=0时,=c3n.设n£m时成立.令,则.例2.错误证明：证.时,,.*错在O(n)的常数c随n的增长而变化，不是常数。*要证明需要证明:对某个c>0,.·直接求和的界限例1.例2.´.例3.设对于所有,，求的上界.解：,,……于是,.例4.求的界解.使用