第三章-函数的增长-3.1-渐近记号

引入：渐近记号的引入是用来刻画算法的运行时间。

一、Θ记号

1、概念

书上原话： 

 如何理解？

存在正 常量c1、c2，使当n足够大的时候，f(n)可以被夹在c1*g(n)和c2*g(n)之间，则称f(n) ∈ θ(g(n))，但是我们通常会表示为f(n) = θ(g(n))，如图，

 在n > n0时，因为f(n)一直被夹在c1g(n)和c2g(n)之间，f(n)在一个常量因子内等于g(n)，因此我们称g(n)为f(n)的一个渐近紧确界（asymptotically tight bound）。

2、要求

θ(g(n))的定义要求每个成员f(n) ∈ θ(g(n))均渐近非负，即f(n)非负（渐近正函数就是对所有足够大的n均为正的函数）。

3、举个例子
我们要证明

 同除n^2得：

 可得c2>=1/2，当no >= 7时，c1<=1/14，因此得证。

二、O记号

1、概念

如何理解?相当于半个θ，只是用于描述上界，下界为0

 2、应用

往往用于描述算法的最坏情况。

三、Ω记号

1、概念

如何理解？

相当于半个θ，只是用于描述下界。

 2、应用

往往用于描述算法的最好情况。

三、o记号

1、概念：

如何理解？

o记号和之前O记号定义类似，但主要的区别是在f(n)=O(g(n))中， 界0<=f(n)<=cg(n)对某个常量c成立，但是在f(n)=o(g(n))中， 界0<=f(n)<cg(n)对所有常量c>0成立,直观来看，当n无限大的时候，情况如下

四、ω记号

1、概念

如何理解？

f(n)=ω(g(n))中 

五、一些性质

1、传递性：

2、自反性 

 3、对称性

 

 4、转置对称性

5、类比，将函数之间比较类比于实数之间的比较