算法设计与分析讲义chapter2

1、第二章 算法分析的数学基础outline 1 算法复杂性的阶 2 和式的估计与界限 3 递归方程 4 集合、关系、函数、图、树等 5 计数原理和概率论2.1 复杂性函数的阶2.1.1同阶函数集合 定义2.1.1(同阶函数集合). q(f(n)=g(n)|$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(n)是非负

2、的，否则=空集。 例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)|$c>0,n0 ,当n³ n0 ,0£g(n)£cf(n)称为比f(n)低阶的函数集合。*如果g(n)ÎO(f(n),称f(n)是g(n)的上界。*g(

3、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)|$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). 证. 如果, 则 当时,. 显然. 如果且,则由可 知，存在使

4、得，当，。由 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. 证明 证. 对, 欲，必，即。所以，当时，对，n³n0。 例2证明证. 当c=1>0时，对于任何, 当，都不成立命题2.1. 证.由于f(n)=o(g(n), 对任意e>0,存在，当时, 0£f(n)<eg(n),即. 于是, .2

5、.1.5 严格高阶函数集合 定义2.1.4(严格高阶函数集合). ， for all 称为严格比g(n)高阶的函数集合。 命题2.2. f(n)Îw(g(n) iff g(n)Îo(f(n). 证：Þ 对，1/c>0. 由知, 对1/c>0,当时,(1/c)g(n)<f(n), 即g(n)<cf(n). 于是, .Ü 对于任意c>0, 1/c>0.由可知, 当时, g(n)<(1/c)f(n)，即cg(n)<f(n). 于是，。 例1证明n2/2=w(n). 证. 对"c>0,cn<n

6、2/2, 只需n>2c.令n0=2c+1, 则当n³n0, cn<n2/2. 例2. 证明n2/2=w(n2). 证. 若n2/2=w(n2)，则对于c=1/2, 存在n0, 当时, cn2<n2/2，即c<1/2，矛盾. 命题2.3. 证：对",由于,必存在n0 ,使得当n³n0时, f(n)>cg(n),即当n³n0时,f(n)/g(n)>c. 于是, .2.1.6 函数阶的性质 A传递性：（a）（b）（c）（d）（e） . B 自反性：（a） ，（b） ，（c） . C 对称性 . D 反对称性： *并非所有函数

7、都是可比的，即对于函数和，可能. 例如, 和.2.2 标准符号和通用函数2.2.1 Flour和ceiling定义2.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 求和公式

8、的性质 1 线性和命题2.4.5 命题2.4.6 证. 对n用数学归纳法证明。 当时，显然成立。假设时成立。 令，则 。 2. 级数 命题2.4.7 命题2.4.8 命题2.4.9 n 命题2.4.10 . 命题2.4.11 命题2.4.12 命题2.4.13 3 和的界限 ·数学归纳法证明 例1. 证明 证 证明对于c³2/3, 存在一个n0 ,当时. 当n=0时, =c3n. 设n£m时成立. 令,则 . 例2. 错误证明： 证. 时,. *错在O(n)的常数c随n的增长而变化，不是常数。 *要证明需要证明: 对某个c>0, . ·直接求和的界

9、限例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排序算法的复杂性方程

10、: T(n)=q(1) if n=1 T(n)=2T(n/2)+q(n) if n>1. T(n)的解是q(nlogn)求解递归方程的三个主要方法: ·Substitution方法: Guess first,然后用数学归纳法证明. ·Iteration方法: 把方程转化为一个和式,然后用和估计技 术求解. ·Master方法: 求解型为T(n)=aT(n/b)+f(n)的递归方程.2.4.1 Substitution方法一般方法: ·猜解的形式 ·用数学归纳法证明猜测的解正确*该方法只能用于解可猜的情况. 1 Make a good gu

11、ess 不幸：无一般的猜测正确解的方法，需要 ·经验 ·机会 ·创造性和灵感 幸运：存在一些启发规则帮助人们去猜测 ·Guess方法：联想类似的已知T(n) 例1. 求解, T(1)=1. 解：展开T(n)若干步,可以猜测T(n)=O(nlogn). 证明T(n)=O(nlogn). 设时或n=m+1时 . 于是,. *边界条件的问题: 设是边界条件，则不成立 *边界条件问题的解决 我们只要求对于时,.我们只需看n=2 n=3，或4等，选一个满足的最小即可。 ,只需,与上界的 不矛盾.例2. 求解. 解: 猜测: 与只相差一个17. 当n充分大时的差别并

12、不大，因为 相差小. 我们可以猜. 证明: 用数学归纳法证明. ·Guess方法：猜测loose上、下界，然后减少不确定性范围 例3. 求解. 解: 首先证明 然后逐阶地降低上界、提高下界。 W(n)的上一个阶是W(nlogn), O(n2)的下一个阶是O(nlogn)。 ·细微差别的处理 问题：猜测正确，数学归纳法的归纳步似乎证不出来 原因：归纳假设不能充分证明 解决方法：从guess中减去一个低阶项，可能work. 例4. 求解 解： 我们猜 证： 证不出 减去一个低阶项，猜，是常数 证：设当时成立 （只要）。 *c必须充分大，以满足边界条件。 ·避免陷阱 例

13、5求解。 解：猜 证：用数学归纳法证明。 -错！ 错在那里：过早地使用了而陷入了陷阱应该在证明 了才可用。从不可能得 到因为对于任何c>0，我们都得不 到. ·变量替换 方法: 经变量替换把一个递归方程变换为我们熟悉的方程. 例6. 求解 解：令，则, . 令则. 于是, . 显然,即 由于2m=n, m=lgn, .2.4.2 Iteration方法 ·方法：循环地展开递归方程，把递归方程转化为和式， 然后可使用求和技术解之。 例1. 令 ·方法的关键： 达到边界条件时，展开需要的循环次数. 由循环递归过程而得到和式. ·注意： 在循环中间可能猜

14、出解，此时应停止循环. floor和ceiling使问题复杂化，我们可以假设方程定义在 一个量的幂，如则可以省略.2.4.3 Master method目的：求解型方程, 是常数， 是正函数 方法：记住三种情况，则不用笔纸即可求解上述方程.1. Master 定理 定理2.4.1 设是常数，是一个函数, 是定义在非负整数集上的函数. 可以如下求解： . 若,是常数，则. . 若，则. 若,是常数, 且对于所有充分大的n , c>1是常数, 则.*直观地：我们用与比较 . 若大，则 . 若大，则 . 若与同阶，则.*更进一步：1. 在第一种情况,不仅小于，必须多项式地小 于,即对于一个常数

15、，2. 在第三种情况,不仅大于，必须多项式地大 于，即对一个常数，.*注意：这三种情况并没有cover 所有可能的 情况1与情况2之间有空隙,即小于,但不是多 项式也小于. 情况2与情况3也同样有间断空隙. 对于这两种情况，Master定理也无能为力. 2. Muster定理的使用 例1.求解. 解：, , 例2. 求解. 解：, , 例3. 求解 解： , 对所有n,. 于是, 例4. 求解.解：.大于，但 不是多项式也大于, Master定理不使用于该.2. Muster定理的证明 ·当，k是正整数 引理1：设a³1, b>1, n=bk, k是正整数， 则方程

16、的解为: 证明: 由于, =. 于是. 引理2: 设a³1, b>1, n=bk, k是正整数， 则(1) if for , 则(2) if , then (3) if for some 0<c<1 and all n³b, then . 证明: (1) (2) 由于, . . (3) g(n)中的所有项皆为正. 由于对于0<c<1和 all n³b, , , , 我们有 于是, 引理3: a³1, b>1, n=bk, k为正整数, 则 的解为: (1) if for some , then (2) if , then (3) if for some , and if for some 0<c<1 and all 充分大的n, then 证明: (1) 由引理1 和引理2: (2) (3) · 当n不是b的幂时 思想: 当T(n)单调递增（单调递减类似） · · 求的上界、的下界 可得到T(n)的界限。 · 求的下界类似于求的上 界，所以我们只求的上界 · 方法仍然是循环展开 · 需要处理序列： n 定义： 引理4. , , , , ，。 证：由可证。 引