渐进符号含义

《渐进符号含义》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、§1.3渐近符号设是算法A的复杂性函数。一般说来，当单调增加趋于时，也将单调增加趋于。如果存在函数，使得当时有，则称是当时的渐近性态，或称是算法A当的渐近复杂性。因为在数学上，是当时的渐近表达式，是中略去低阶项所留下的主项，所以它无疑比来得简单。进一步分析可知，要比较两个算法的渐近复杂性的阶不相同时，只要确定出各自的阶，就可以知道哪一个算法的效率高。换句话说，渐近复杂性分析只要关心的阶就够了，不必关心包含在中的常数因子。所以，我们常常有对的分析进一步简化，即假设算法中用到的所有不同的运算（基本）各执行一次所需要的时间都是一个单位时间。综上分析，我们已经给出了简化算法复

2、杂性分析的方法和步骤，即只考虑当问题的规模充分大时，算法复杂性在渐近意义下的阶。为此引入渐近符号，首先给出常用的渐近函数。常用的渐进函数函数名称函数名称1常数n2平方logn对数n3立方n线性2n指数nlognn倍lognn！阶乘在下面的讨论中，用f(n)表示一个程序的时间或空间复杂性，它是实例特征n（一般是输入规模）的函数。由于一个程序的时间或空间需求是一个非负的实数，我们假定函数f(n)对于n的所有取值均为非负实数，而且还可假定n>=0。渐近符号O的定义：f(n)=O(g(n))当且仅当存在正的常数c和n0，使得对于所有的n>=n0，有f(n)<=cg(n)。此时

3、，称g(n)是f(n)的一个上界。函数至多是函数的倍，除非。即是说，当n充分大时，是的一个上界函数，在相差一个非零常数倍的情况下。通常情况下，上界函数取单项的形式，如表1所列。C0=O(1):f(n)等于非零常数的情形。3n+2=O(n):可取c＝4，n0＝2。100n+6=O(n):可取c=101，n0＝6。10n2+4n+3=O(n2):可取6×2n+n2=O(2n):可取c=7，n0=4.3×logn+2×n+n2=O(n2).n×logn+n2=O(n2).3n+2=O(n2).三点注意事项：1．用来作比较的函数g(n)应该尽量接近所考虑的函数f(n).3n+

4、2=O(n2)松散的界限；3n+2=O(n)较好的界限。2．不要产生错误界限。n2+100n+6，当n<3时，n2+100n+6<106n，由此就认为n2+100n+6＝O(n).事实上，对任何正的常数c，只要n>c-100就有n2+100n+6>c×n。同理，3n2+4×2n=O(n2)是错误的界限。3．f(n)=O(g(n))不能写成g(n)=O(f(n))，因为两者并不等价。实际上，这里的等号并不是通常相等的含义。按照定义，用集合符号更准确些：O(g(n))={f(n)

5、f(n)满足：存在正的常数c和n0，使得当n>=n0时，f(n)<=cg(n)}所以，人们常

6、常把f(n)=O(g(n))读作：“f(n)是g(n)的一个大O成员”。大O比率定理：对于函数和，如果极限存在，则当且仅当存在正的常数c，使得.证明：略。例子因为，所以；因为，所以；因为，所以；因为，所以，但是这不是一个好的上界估计，问题出在极限值不是正的常数。下述不等式对于复杂性阶的估非常有帮助：定理2.3.1.对于任意一个正实数和，有下面的不等式：1)存在某个使得对于任何，有。2)存在某个使得对于任何，有。3)存在某个使得对于任何，有。4)存在某个使得对于任何，有。5)对任意实数，存在某个使得对于任何，有。例子根据定理1，我们很容易得出：；；。