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