《算法的渐进复杂度分析.pps》由会员分享，可在线阅读，更多相关《算法的渐进复杂度分析.pps（36页珍藏版）》请在三一文库上搜索。
1、具体数学 Concrete Mathematics,赵启阳 2019年2月24日星期日,北京航空航天大学计算机学院,2019/2/24,2,9 渐进 Asymptotics,2019/2/24,3,渐进处理的意义,在实际研究或应用中遇到的数学问题中，精确答案往往是可遇不可求的 （1）有的问题并没有封闭形式解； （2）封闭形式解存在，但是以现在的数学工具很难求出。 近似结果往往能够满足实际需要，因此了解渐进意义下的变化趋势也很有价值和意义。,2019/2/24,4,渐进处理的例子,对于求和问题 这个问题看上去是没有封闭形式解的。但是有 这对判断Sn的变化趋势是很有帮助的。此时称Sn渐进于,201
2、9/2/24,5,渐进处理的例子,如果进一步给出 显然就更加精确了，因为它指出我们渐进的相对误差大概是 然而在面对渐进趋势与Sn相近的量例如斐波那契数F4n时，怎样判断它们之间的大小关系？,2019/2/24,6,渐进处理的例子,当n=2时， 。当n趋向于无穷大时 因此还是F4n要大一些。这个结果看上去很难导出，本章的目的就是学习相关的技巧，使我们可以方便快捷地推导出这样的结果。,2019/2/24,7,渐进处理名称的来源,渐进（Asymptotics）来自于希腊语，字面意义是“不落在一起”。古希腊数学家研究双曲线 时发现当x趋向于无穷时，双曲线无限逼近但不会碰到直线 现在我们提到“渐进”，重
3、点强调“越来越趋近”。,2019/2/24,8,9.1 量的等级 A Hierarchy,2019/2/24,9,量的等级,第一个关系符号 ：某个函数比另一个函数的增长趋势更快 传递性： 使用符号 可对常见的函数做一个排序,计算复杂度取这些函数的算法有哪些？,2019/2/24,10,量的等级,上面排序中的函数都趋向于无穷大。还有另外一种趋向于0的排序 事实上如果有 对于其它函数，可以尝试放到这个序列的合适位置,2019/2/24,11,量的等级,例如，对于小于等于n的素数个数函数 由于 近似等于 ，而 因此 即 例如，对于函数 由于 因此,2019/2/24,12,量的等级,当两个函数的增长
4、率相同时，写成 正式定义为 例如对于 事实上，如果f(n)和g(n)是次数相同的多项式即有此关系。 更强的关系：函数f渐进于函数g,2019/2/24,13,量的等级,G.H. Hardy 提出的对数指数函数类（logarithmico-exponential function）： （1）所有常数函数在类中； （2）恒等函数f(x)=x在类中； （3）如果函数f、g在类中，那么函数f-g也在类中； （4）如果函数f在类中，那么函数ef也在类中； （5）如果函数f在类中而且最终取正值，那么lnf也在类中。 问题：如果函数f在类中，如何证明函数f0.5也在类中？,2019/2/24,14,量的等级
5、,关于以上函数类，哈代给出一个定理： 函数类中的所有函数构成一个渐进等级：如果f、g属于该函数类，那么必有以下三种情况之一 在第三种情形中，必有某个常数，使得 哈代函数类包含了几乎所有感兴趣的函数，因此可以将任意给定函数放进给定的渐进等级中。,2019/2/24,15,9.2 大O记号 O Notation,2019/2/24,16,大O记号,1894年，Paul Bachmann引入了大O记号 大O记号在计算复杂度分析中常常遇到，它的作用是可以让我们忽略细节。 我们说 如果有某个常数c，使得 当大O记号出现在某个公式中时，代表一个满足以上定义的函数f。 例如对于前n个正整数平方之和，有,20
6、19/2/24,17,大O记号,上述定义可以推广到任意实数函数，但是需要给出自变量的范围。在一般情况下，这个范围由某个极限关系来描述，例如 需要注意，带有大O记号的等式不能反过来写。严格地讲，大O记号指的是满足 的所有函数f构成的集合。 因此前面等式中的“=”严格地应写成“”。,2019/2/24,18,大O记号,与大O记号相对应，还有记号大、大和小o。 大： 大： 小o：,2019/2/24,19,9.3 大O的运算 O Manipulation,2019/2/24,20,大O的运算,关于大O的运算规则： （1） （2） （3） （4） （5） 在计算中，可以用右边的式子代替左边的式子。,2
7、019/2/24,21,大O的运算,大O的运算常用在幂级数的求和中。如果求和式 对于某个复数z=z0绝对收敛，那么 特别地，如果S在某个非零的z上收敛，那么有,2019/2/24,22,大O的运算,由此导出大O记号对幂级数求和的截断操作，例如 因为 而第二个求和式在z0上绝对收敛，因此对于所有趋向于0的z来说等于O(1)。,2019/2/24,23,大O的运算,某些函数的大O记号形式 大O记号并不是只能用于绝对收敛（甚至条件收敛）的级数求和。在上表中Hn、n!、(n)都不收敛，但是采用大O记号来近似仍然是有意义的。,2019/2/24,24,大O的运算,如果某个渐进形式为f+O(g)，而且其中
8、的f部分不包含大O记号，那么就称这个渐进形式的绝对误差为O(g)。 如果某个渐进形式为f(1+O(g)，而且其中的f部分不包含大O记号，那么就称这个渐进形式的相对误差为O(g)。 利用幂级数截断操作可以证明两条一般性结论： 综合这两条结论可以得到,2019/2/24,25,大O运算的具体例子,第三章：幸运轮盘中取胜位置的个数 渐进表示： （1）用N1/3+O(1)代替K，去掉下取整符号并得到 （2）根据前面的运算规则，有,2019/2/24,26,大O运算的具体例子,同样地有 代入到W的式子，得到,2019/2/24,27,大O运算的具体例子,斯坦福大学1970-1971学期具体数学的一道试题
9、： 求解求和式 的绝对误差为O(n-7)的渐进形式。 首先提取每一项的主要部分，得到 这样逐项加起来，即可利用前n个正整数的平方之和、立方之和、四次方之和、8次方之和得到所要求的结果非常麻烦的过程,2019/2/24,28,大O运算的具体例子,这里有一个更巧妙的方法，使用调和数的渐进结论。我们有 而且已知 到这里已经可以直接求差得到理想的结果了。如果更进一步，要把它表示成幂级数的话，再对对数项进行化简。,2019/2/24,29,大O运算的具体例子,首先有 加起来之后会有很多项抵消掉，得到,2019/2/24,30,大O运算的具体例子,关于Solomon Golomb提出的渐进问题：求解 的渐
10、进值。Nn(k)为将k表示成n进制数时的位数。 首先给出大致估计： 位数Nn(k)近似为lognk=logk/logn 因此和式中的项大致等于(logn)2/klog(k)2 再对k求和得到近似值 最终得到Sn大约为C(logn)2。,2019/2/24,31,大O运算的具体例子,为了更加精确地分析Sn，首先给出Nn(k) 从而有 如果以lognk+O(1)替换Nn(k)，那么O(1)总是在01之间，平均起来大约0.5左右，但是这对比较小的k来说，（相对）误差有些太大。,2019/2/24,32,大O运算的具体例子,为了避免Nn(k)带来的误差，首先将Sn的求和式处理成更容易的方式，令m=Nn
11、(k)，则 到这里出现了调和数，可以考虑用调和数的近似了！,2019/2/24,33,大O运算的具体例子,使用分布和分法，继续化简Sn得到 由于 因此Sn化为,2019/2/24,34,大O运算的具体例子,首先处理3 注意到这是一个幂级数（x=1时收敛），因此可以在任意的项数上截断。如果在k=2时截断，那么得到 相应地，如果在k=1时截断就得到,2019/2/24,35,大O运算的具体例子,接着处理2 这是一个叠缩级数求和问题，很显然结果为1 最后考虑1,二阶调和数！,2019/2/24,36,大O运算的具体例子,将各项加在一起，即得到Sn的估计值 这比原来用连续积分的近似值C(logn)2的增长趋势要慢多了。这个例子说明，如果用比较粗略的连续近似，有时对离散求和问题的误差是比较大的,