函数的增长
1.渐进记号
Θ记号
定义：
对于一个给定的函数g()
用Θ(g(n))来表示以下函数的集合
Θ(g(n))={f(n):存在正常量c1、c2和N,使得对所有的n>=N,有0<=c1*g(n)<=f(n)<=c2*g(n)}
注：这里我们通常已知f(n)求g(n)
函数如下图：
这时我们称g(n)是f(n)的一个渐进紧确界
即当n逐渐变大的时候，对于f(n)，只需取f(n)中较有决定性的项A，即当n变大到一定程度时，A变化相对与其他项非常明显，例如
多项式的幂最高项。而c1,c2的选取，只需要c1略小于A的系数，c2略大于A的系数，这样就可以保证，当n大到一定程度时，f(n)在
两者中间。现在知道f(n)，要求g(n)，就找出其A，进而得到g(n)。
直觉上，一个渐进正函数的低阶项在确定渐进确界时可以被忽略，因为对大的n,它们是无足轻重的。当n较大时，即使是最高阶的一
个很小的部分就足以支配所有低阶项。
一般来说，对任意多项式p(n)=a[1]*n^1+a[2]*n^2+a[3]*n^3+….+a[d]*n^d;
其中a[]为常数，且a[d]>0
则p(n)=Θ(n^d);
如果是0阶，则可以表示为Θ(1)
O记号
Θ记号渐进地给出一个函数的上界和下界，当只有一个渐进上界时用O记号。
定义：
O(g(n))={f(n):存在正常量c、N,使得对所有的n>=N,有0<=f(n)<=c*g(n)}
因为Θ(g(n))是一个比O(g(n))更强的概念，所以有Θ(g(n))属于O(g(n))
使用O记号，我们常常可以仅仅通过检查算法的总体结构来描述算法的运行时间。
当我们说“运行时间为O(n^2)”时，意指存在一个O(n^2)的函数f(n)，使得对n的任意值，不管选择什么特定的规模
为n的输入其运行时间的上界都是f(n)。这也就是所说的最坏的运行时间为O(n^2)。
Ω记号
与O记号相反，Ω记号提供了一个渐进下界，
定义：
Ω(g(n))={f(n):存在正常量c、N,使得对所有的n>=N,有0<=c*g(n)<=f(n)}
根据其性质，我们有以下定理：
对任意两个函数f(n)和g(n)，我们有f(n)=Θ(g(n))，当且仅当f(n)=O(g(n))和f(n)=Ω(g(n))
当称一个算法的运行时间为Ω(g(n))，就是指对于每个n值，不管选择什么特定的规模为n的输入，只要n足够大，对
那个输入的运行时间至少是g(n)的常量倍。
例如插入排序运行时间介于Ω(n)和O(n^2),即其最好情况为一次线性函数，最坏情况为二次线性函数。
o记号
定义：
o(g(n))={f(n):对于任意正常量c、N,使得对所有的n>=N,有0<=f(n)<=c*g(n)}
2*n=o(n^2) 2*n!=o(n)
当n趋于正无穷时，函数f(n)对g(n)就变的微不足道了即
lim(n->∞) f(n)/g(n)=0;
ω记号
ω与Ω的关系和o与O的关系类似
定义：
ω(g(n))={f(n):任意正常量c、N,使得对所有的n>=N,有0<=c*g(n)<=f(n)}
n^2=ω(n) n^2!=ω(n^2)
即
lim(n->∞) f(n)/g(n)=∞;
记号的几种性质：
传递性：
f(n)=o(g(n))&&g(n)=o(h(n))得到f(n)=o(h(n))
f(n)=O(g(n))&&g(n)=O(h(n))得到f(n)=O(h(n))
f(n)=ω(g(n))&&g(n)=ω(h(n))得到f(n)=ω(h(n))
f(n)=Ω(g(n))&&g(n)=Ω(h(n))得到f(n)=Ω(h(n))
f(n)=Θ(g(n))&&g(n)=Θ(h(n))得到f(n)=Θ(h(n))
自反性：
f(n)=Θ(f(n))
f(n)=Ω(f(n))
f(n)=O(f(n))
对称性：
f(n)=Θ(g(n))<=>g(n)=Θ(f(n))
转置对称性：
f(n)=O(g(n))<=>g(n)=Ω(f(n))
f(n)=o(g(n))<=>g(n)=ω(f(n))
用两个实数来表示两者的关系:
f(n)=o(g(n)) a > b
f(n)=O(g(n)) a>=b
f(n)=ω(g(n)) a < b
f(n)=Ω(g(n)) a<=b
f(n)=Θ(g(n)) a = b
等式和不等式中渐进记号
1.对于在等式右侧的渐进符号来说，其代表了一个匿名的函数，该函数属于该渐进符号
例如n=O(n)可以表示为n=f(n) f(n)属于O(n)
2.理论上有几个渐进符号就有几个匿名等式。
∑O(i)也只有一个匿名函数，而O(1)+O(2)+...+O(n)则有多个
3.对于n+O(n)=O(n^3)这中情况，可以理解为：无论怎样选择符号左边的匿名函数，总有一种办法来选择等号右边的
匿名函数使等式
成立。
标准标记和常用函数
由于一些函数已经很熟悉，这里不再赘述
1.单调性
2.向上取整，向下取整
3.模运算
4.多项式
5.指数
6.阶乘
7.多重函数：即递归定义
8.多重对数函数
9.斐波那契数列