渐进符号
1、Θ记号 Θ(g(n)) = { f(n) : 若存在正常数c1,c2和n0,使对所有n>=n0时有0<=c1g(n)<=f(n)<=c2g(n)}
其效果相当于删除f(n)中的低阶项，并忽略最高阶项的系数。
2、Ο记号 Ο(g(n)) = { f(n) : 存在正常数c和n0,使对所有n>=n0,有0<=f(n)<=c*g(n) }
Ο记号在一个常数因子内给出某函数的一个上界。f(n) = Ο(g(n))表示f(n)是集合O(g(n))的一个元素。f(n) = Θ(g(n))隐含着f(n) = Ο(g(n)),因为Θ记号强于Ο记号。对f(n) = Ο(g(n))只能说明g(n)的某个常数倍是f(n)的渐近上界，而不反映该上界如何接近。Ο记号在用作对算法最坏情况运行时间的上界时就有对任意输入的运行时间的上界。
3、Ω记号 Ω(g(n)) = { f(n) : 存在正常数c和n0,使所有n>=n0有0<=c*g(n)<=f(n) }
Ω记号给出一个函数的渐近下界。
对于上面三种，有下面的定理：
对任意两个函数f(n)和g(n),f(n) = Θ(g(n))当且仅当f(n) = Ο(g(n))和f(n) = Ω(g(n)).
4、其它符号
ο记号：Ο记号提供的渐近上界可能是也可能不是渐近紧确的。2n^2 = Ο(n^2)是渐近紧确的，而2n = O(n^2)不是。而o记号用来表示非渐近紧确的。 o(g(n)) = { f(n) : 对任意正常数c，存在正常数n0,使对所有n>=n0,有0<=f(n)<=c*g(n) }
ω记号：ω记号与Ω记号的关系和o记号与Ο记号的关系一样，不在多说。
总之，可以这样理解，Θ记号相当于"=",Ο相当于“<=",Ω相当于”>=",o相当于“<",ω相当于">".这样理解只用于区别不同渐近记号间的关系，其实每个渐近记号为一个函数集合，而非两个数关系那样的。
________________________________________-
对于任何数学函数，这三个记号可以用来度量其“渐近表现”，即当趋于无穷大时的阶的情况，这是算法分析中非常重要的概念。大家可以把它们分别想象成≤、≥和 =，分别估计了函数的渐近上界、渐近下界和准确界。诚然，渐近关系和确切大小关系是有区别的，但当问题规模很大时，忽略这种区别能大大降低算法分析的难度。
设函数f ( n )代表某一算法在输入大小为n的情况下的工作量（效率），则在n趋向很大的时候，我们将f (n)与另一行为已知的函数g(n)进行比较：
1）如果=0，则称f (n)在数量级上严格小于g(n)，记为f (n)=o( g(n))。
2）如果无穷，则称f (n)在数量级上严格大于g(n)，记为f (n)=ω ( g(n))。
3）如果=c，这里c为非0常数，则称f (n)在数量级上等于g(n)，即f (n)和g(n)是同一个数量级的函数，记为：f (n)=Θ( g(n))。
4）如果f (n)在数量级上小于或等于g(n)，则记为f (n)=O( g(n))。
5）如果f(n)在数量级上大于或等于g(n)，则记为f (n)=Ω( g(n))。
这里我们假定f (n)，g (n)是非负单调的，且极限存在。如果这个极限不存在，则无法对f (n)和g (n)进行比较。在进行此种计算时，一个经常用到的技术是洛必达（L'Hopital）法则。该法则由17世纪法国数学家Guillaume de L'Hopital发现（也有人认为是瑞士数学家Johann Bernoulli发现的）。该法则声称，两个函数的比率极限等于两个函数的导数的比率极限，这里当然假定两个函数的导数比率的极限存在，即有：
有了这个定义，就可以对素性测试的两个算法进行比较了。
符合第1个定义，因此这两个素性测试算法的效率差异是数量级的差异。
在算法分析中，最常选取的g(n)有如下一些：
参考文章
http://blog.csdn.net/shadow132/article/details/50546834
求和的基本公式
对无穷几何级数求导再同乘以x可得：
再求导，乘x：
