第二章第二章 算法分析的数学基础算法分析的数学基础 DB-LAB (2003)2.1.1 同阶函数集合同阶函数集合 2.1.2 低阶函数集合低阶函数集合 2.1.3 高阶函数集合高阶函数集合 2.1.4 严格低阶函数集合严格低阶函数集合 2.1.5 严格高阶函数集合严格高阶函数集合 函数阶的性质函数阶的性质 计算复杂性函数的阶计算复杂性函数的阶 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 证明证明 证证. . 如果存在如果存在c c1 1、c c2 2 0 0，n n0 0使得当使得当n n n n0 0时，时，c c1 1 6n6n3 3 c c2 2 n n2 2 。于是，当。于是，当n n c c2 2 /6/6时，时， n n c c2 2 /6/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 Flour 和和 ceilingceiling 多项式多项式 标准符号和通用函数标准符号和通用函数 DB-LAB (2003) FlourFlour和和ceilingceiling DB-LAB (2003) DB-LAB (2003)如果如果f(n)=O(nk), 则称则称f(n)是多项式界限的。是多项式界限的。 DB-LAB (2003)1. 1. 线性和线性和 和式的估计与界限和式的估计与界限 DB-LAB (2003)2. 2. 级数级数 DB-LAB (2003) DB-LAB (2003)3. 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)递递归归方方程程: : 递递归归方方程程是是使使用用小小的的输输入入值值来来描描述述 一个函数的方程或不等式一个函数的方程或不等式. . 递归方程递归方程 递归方程例递归方程例: : Merge-sort排序算法的复杂性方程排序算法的复杂性方程 T(n)= (1) if n=1 T(n)=2T(n/2)+ (n) if n1. T(T(n n) )的解是的解是 ( (n nloglogn n) ) DB-LAB (2003)Substitution方法方法:Guess first,Guess first,然后用数学归纳法证明然后用数学归纳法证明. .Iteration方法方法: : 把方程转化为一个和式把方程转化为一个和式然后用估计和的方法来求解然后用估计和的方法来求解. .Master方法方法: : 求解型为求解型为T(n)=aT(n/b)+f(n)的递归方程的递归方程 求解递归方程的三个主要方法求解递归方程的三个主要方法 DB-LAB (2003)Substitution方法方法：联想已知的：联想已知的T(n) 例1. 求解2T(n/2 + 17) + n2.4.1 Substitution方法方法 证明：用数学归纳法 DB-LAB (2003)SubstitutionSubstitution方法方法：猜测上下界，减少不确定性范围猜测上下界，减少不确定性范围 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 Master 定理定理 DB-LAB (2003)T(n)= (nlogba)T(n)= (f(n)f(n)f(n) (f(n)lgn)nn-对于红色部分，对于红色部分，Master定理无能为力定理无能为力 DB-LAB (2003) DB-LAB (2003)Master定理的使用定理的使用 DB-LAB (2003)MasterMaster定理的使用定理的使用（续）（续） 地地地地适适适适 DB-LAB (2003)Master定理的证明定理的证明 bi DB-LAB (2003)Master定理的证明定理的证明( (续续) ) DB-LAB (2003)引理引理2的证明的证明 DB-LAB (2003)引理引理2 2的证明（续）的证明（续） DB-LAB (2003)引理引理2 2的证明（续）的证明（续） ( (f(n)f(n) ) DB-LAB (2003)Master定理的证明定理的证明( (续续) ) DB-LAB (2003)引理引理3 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 7的证明的证明 DB-LAB (2003)引理引理7 7的证明的证明 DB-LAB (2003)引理引理7 7的证明的证明