用“渐近记号”来表示“渐近复杂度”。
1. 渐近记号包括：
(1)Θ（西塔）：紧确界。 相当于"="
(2)O （大欧）：上界。 相当于"<="
(3)o（小欧）：非紧的上界。 相当于"<"
(4)Ω（大欧米伽）：下界。 相当于">="
(5)ω（小欧米伽）：非紧的下界。 相当于">"
给出这些记号的定义：
注解：渐近非负的意思是“当n趋于无穷大时，f(n)和g(n)都非负”。
2. 用集合论来表示这5个符号的关系：
从上面的图可以看出：
(1)如果f(n)=Θ(g(n)),则f(n)=O(g(n))且f(n)=Ω(g(n))。
(2)如果f(n)= o (g(n)),则f(n)=O(g(n))。
(3)如果f(n)=ω(g(n))，则f(n)=Ω(g(n))。
因此对于这些渐近记号的使用最准确应该是“f(n)∈ O (g(n))”，但是一般都是写成“f(n)=O(g(n))”。
给出一些例子：
O(n^2)可以是n,2n,1,2n^2等。
Θ(n^2)可以是n^2,3n^2等。
ω(n^2)可以是n^3,n^10等,但不能是n^2。
Ω(n^2)可以是n^2,n^3,n^10等。
o(n^2)可以是n,1,3n等,但不能是n^2。
我们这里给出了很通用的方法，叫做“极限法”。
看到上面的方法，很多人会问“怎么没有 O 和Ω？”，原因很简单，因为如果f(n)=O(g(n)),则要么是f(n)= o (g(n))，要么是f(n)=Θ(g(n))。
4. 相关法则
5. 常用的函数阶
下面是在分析算法的时候常见的函数分类列表。所有这些函数都处于趋近于无穷大的情况下，增长得慢的函数列在上面。是一个任意常数。
符号 |
名称 |
常数（阶，下同） |
|
对数 |
|
多对数 |
|
线性，次线性 |
|
为迭代对数 |
|
线性对数，或对数线性、拟线性、超线性 |
|
平方 |
|
多项式，有时叫作“代数”（阶） |
|
指数，有时叫作“几何”（阶） |
|
阶乘，有时叫做“组合”（阶） |