在算法分析中，经常会遇到以下几种渐进符号
渐近边界符号：(big-theta )渐近上界符号： oo ) big-oh )渐近下界符号：) big-omege )非渐近上界： o (小-oh )非渐近下界确定()小-omege ) 3358ww
下面对渐进符号进行详解：
f(n )=o ) g(n )，这里为f ) n )是分析后的算法执行次数的函数，
大写O符号仅当且存在正常数c和n0时，对于所有n=n0存在f(n )=CG (n )。
这里，cg(n是函数f[n]的上限。 要说这是不是很模糊，我一开始也是。 别急，看下面这个例子，你会恍然大悟的。
几个函数的例子：
O的定义：
当f(n )=3n 2且n=2时，3n 2=3n n=4n。
因此，如果f(n )=o )，其中c=4，n0=2，g(n )=n，则CG )，n )，即4n为f )的上界
1.线性函数
f(n ) 4nn^2) 3n3，n=3时，3n 3=4n，n=4时，4nn^2，f(n )=2n^2 n^2=3n^2。
f(n )=o ) n^2)，其中c=3，n0=4，g ) n )=n^2，则CG ) n )即3n^2是f ) n )的上界
2.平方函数
f(n )=6*2^n ) 2、n=4时，n ) n^2=2^n，所以n=4时，f ) n )=6*2^n 2^n=7*2^n。
其中c为7，n0=4，f(n )=o )2^n )。
3.指数函数
f(n )=9，在此直接为o ) ) 1，c为9，n0为0即可，设f(n )=9=9*1。
4.常数阶
3358www.Sina.com/f(n )=) g ) n )，且仅当存在正常数c和n0时，才存在所有n=n0的f ) n )=CG ) n )。
符号是赋予函数的下限。
符号
由于对于所有的n都有f(n )=3n 23n，所以f ) n )=)，此处c=3，n0=0。 在此也如f(n )=)1)所示，
定义：
如果存在大于例子：的常数c1、c2和非负整数n0以及足够大的n，则对于所有nn0存在c1g(n )=f
(n )=c2g(n ) n。
3358www.Sina.com/3n2=(n )在c1=3，c2=4，n=n0=2的情况下，3n=3n 2=4n。
符号
3358www.Sina.com/f(n )=o ) g ) n )，且f ) n )=o ) g ) n )且f ) n )！=(g ) n )。
定义：