资源描述
第二章 算法分析的数学根底outline 1 算法复杂性的阶 2 和式的估计与界限 3 递归方程 4 集合、关系、函数、图、树等 5 计数原理和概率论2.1 复杂性函数的阶.1同阶函数集合 定义2.1.1(同阶函数集合). q(f(n)=g(n)|$c1,c20,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(n)是非负的，否如此=空集。 例1 证明 证. 设 ，令c1=a/4, c2=7a/4,如此， 令。当时成立。 例2 证明 证. 如果存在c1、c2 0，n0使得当nn0时，c16n3c2n2。于是，当nc2/6时，nc2/6，矛盾。 例3 例4 因任何常数，如果令 。2.1.2 低阶函数集合定义2.1.2(低阶函数集合).O(f(n)=g(n)|$c0,n0,当n n0 ,0g(n)cf(n)称为比f(n)低阶的函数集合。*如果g(n)O(f(n),称f(n)是g(n)的上界。*g(n)O(f(n)常记作g(n)=O(f(n)。 例1 例2 证明 。证. 令c=1,n0=1,如此当时，。2.1.3 高阶函数集合定义2.1.3(高阶函数集合).W(f(n)=g(n)|$c0,n0,当n n0 ,0cf(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(n)=W(g(n)可知，使得当， 令,如此当，。2.1.4. 严格低阶函数集合定义2.1.4(严格低阶函数集合). for all 称为严格比g(n)低阶的函数集合。*如果f(n)o(g(n),称g(n)是f(n)的严格上界。*f(n)o(g(n)常记作f(n)=o(g(n)。例1. 证明 证. 对, 欲，必，即。所以，当时，对，nn0。 例2证明证. 当c=10时，对于任何, 当，都不成立命题2.1. 证.由于f(n)=o(g(n), 对任意e0,存在，当时, 0f(n)0. 由知, 对1/c0,当时,(1/c)g(n)f(n), 即g(n)0, 1/c0.由可知,当时,g(n)(1/c)f(n)，即cg(n)0,2c.令n0=2c+1, 如此当nn0,n2/2.例2. 证明n2/2=w(n2).证. 假如n2/2=w(n2)，如此对于c=1/2, 存在n0, 当时,2n2/2，即ccg(n),即当nn0时,f(n)/g(n)c. 于是, .2.1.6 函数阶的性质A传递性：（a）（b）（c）（d）（e） .B 自反性：（a） ，（b） ，（c） .C 对称性.D 反对称性： *并非所有函数都是可比的，即对于函数和，可能. 例如, 和.标准符号和通用函数2.2.1 Flour和ceiling定义2.2.1(Flours和ceiling).表示小于或等于x的最大整数. 表示大于等于x的最小整数. 对于任意函数n,证. 假如,如此，. 于是 假如 n=2k+1, 如此. 设n、a、b是任意整数，如此(1)。(2)证.(1) 假如,如此。 假如，00, .直接求和的界限例1. 例2. . 例3. 设对于所有,，求的上界. 解：, , 于是, . 例4. 求 的界 解. 使用例3的方法. . 于是. 例5. 用分裂和的方法求的下界. 解: . 例6. 求 的上界 解：当时, 于是 =O(1).例7. 求的上界 解： 例8. 如果单调递增, 如此.f(x)f(x)m-1 m m+1 m+2 nf(x), ,m-1 m m+1 m+2.n-2 n-1 n n+1 例9. 当单调递减时,. 例10. , .2.4 递归方程递归方程: 递归方程是使用小的输入值来描述一个函数的方程或 不等式.递归方程例: Merge-sort排序算法的复杂性方程:T(n)=q(1) if n=1 T(n)=2T(n/2)+q(n) if n1. T(n)的解是q(nlogn)求解递归方程的三个主要方法:Substitution方法: Guess first,然后用数学归纳法证明.Iteration方法: 把方程转化为一个和式,然后用和估计技 术求解.Master方法: 求解型为T(n)=aT(n/b)+f(n)的递归方程.2.4.1 Substitution方法一般方法: 猜解的形式用数学归纳法证明猜想的解正确*该方法只能用于解可猜的情况.1 Make a good guess不幸：无一般的猜想正确解的方法，需要经验机会创造性和灵感幸运：存在一些启发规如此帮助人们去猜想Guess方法：联想类似的T(n) 例1. 求解, T(1)=1. 解：展开T(n)假如干步,可以猜想T(n)=O(nlogn). 证明T(n)=O(nlogn). 设时或n=m+1时. 于是,. *边界条件的问题: 设是边界条件，如此不成立 *边界条件问题的解决 我们只要求对于时,.我们只需看n=2n=3，或4等，选一个满足的最小即可。,只需,与上界的不矛盾.例2. 求解. 解:猜想: 与只相差一个17. 当n充分大时的差异并不大，因为相差小. 我们可以猜. 证明: 用数学归纳法证明.Guess方法：猜想loose上、下界，然后减少不确定性围 例3. 求解. 解: 首先证明 然后逐阶地降低上界、提高低界。W(n)的上一个阶是W(nlogn), O(n2)的下一个阶是O(nlogn)。细微差异的处理问题：猜想正确，数学归纳法的归纳步似乎证不出来 原因：归纳假设不能充分证明 解决方法：从guess中减去一个低阶项，可能work. 例4. 求解解： 我们猜 证： 证不出 减去一个低阶项，猜，是常数 证：设当时成立只要。 *c必须充分大，以满足边界条件。防止陷阱 例5求解。 解：猜 证：用数学归纳法证明。-错！ 错在那里：过早地使用了而陷入了陷阱应该在证明 了才可用。从不可能得 到因为对于任何c0，我们都得不 到.变量替换 方法: 经变量替换把一个递归方程变换为我们熟悉的方程. 例6. 求解 解：令，如此, . 令如此. 于是, . 显然,即 由于2m=n, m=lgn, .2.4.2 Iteration方法方法：循环地展开递归方程，把递归方程转化为和式， 然后可使用求和技术解之。 例1.令方法的关键： 达到边界条件时，展开需要的循环次数. 由循环递归过程而得到和式.注意： 在循环中间可能猜出解，此时应停止循环.floor和ceiling使问题复杂化，我们可以假设方程定义在 一个量的幂，如如此可以省略.2.4.3 Master method目的：求解型方程, 是常数，是正函数方法：记住三种情况，如此不用笔纸即可求解上述方程.1. Master 定理定理2.设是常数，是一个函数, 是定义在非负整数集上的函数. 可以如下求解：. 假如,是常数，如此. 假如，如此. 假如,是常数, 且对于所有充分大的n , c1是常数, 如此.*直观地：我们用与比拟. 假如大，如此. 假如大，如此. 假如与同阶，如此.*更进一步：. 在第一种情况,不仅小于，必须多项式地小 于,即对于一个常数，. 在第三种情况,不仅大于，必须多项式地大于，即对一个常数，.*注意：这三种情况并没有cover 所有可能的情况1与情况2之间有空隙,即小于,但不是多 项式也小于.情况2与情况3也同样有连续空隙.对于这两种情况，Master定理也无能为力.2. Muster定理的使用. 解：, , 例2. 求解. 解：, 例3. 求解 解：, 对所有n,. 于是, 例4. 求解.解：.大于，但 不是多项式也大于, Master定理不使用于该.2. Muster定理的证明当，k是正整数 引理1：设a1, b1, n=bk, k是正整数， 如此方程的解为: 证明: 由于,=. 于是. 引理2: 设a1, b1, n=bk, k是正整数， 如此(1) if for , 如此(2) if , then (3) if for some 0c1 and all nb, then . 证明: (1) (2) 由于, . . (3) g(n)中的所有项皆为正. 由于对于0c1, n=bk, k为正整数, 如此 的解为: (1) if for some , then (2) if , then (3) if for some , and if for some 0c1 and all 充分大的n, then 证明: (1) 由引理1 和引理2: (2) (3) 当n不是b的幂时 思想: 当T(n)单调递增单调递减类似求的上界、的下界 可得到T(n)的界限。 求的下界类似于求的上 界，所以我们只求的上界 方法仍然是循环展开 需要处理序列： n定义： 引理4., , , , ，。 证：由可证。引理5：当时, 证:由于，我们有。引理6: 证: 引理7:可以界限如下：（1） If for ,.（2） If , then .（3） If for 0c1 and all 充分大的n, then .证明：3由有: 证明的其余局部与引理2的3的证明类似。 2只要证明，即可用引理2的2 的证明完本钱证明。 由于，使对于充分大的，是常数 于是2被证明。 (1) 只要证明，如此本证明的其余局部与引理2的1 一样。类似2可证明。 至此，我们完成了Master定理的证明。19 / 19
展开阅读全文