1. 写在最先面
上一篇博客介绍了算法的一些基本知识，包括算法的证明、算法的分析、算法的设计，这一篇就算法分析中的复杂度的表示方法，作进一步的说明。
2. 渐进记号
Θ 记号
在上一章中，我们记 插入排序 的最坏运行时间为：T(n) = Θ(n²)。下面对这种表示法给出严格的定义：
θ(g(n)) = {f(n)：存在正常量c1，c2，n0，使得对所有n ≥ n0，有0 ≤ c1 * g(n) ≤ f(n) ≤ c2 * g(n)}
通俗地讲即为：
若存在正常数才c1，c2，使得对于足够大的n，函数f(n)能“夹入”c1g(n)与c2g(n)之间，则f(n)属于集合θ(g(n))（通常把f(n) ∈ θ(g(n))记为f(n) = θ(g(n))）。
这时，我们称g(n)是f(n)的一个渐进紧确界。
图像表示如下：
Ο记号
Θ记号渐进的给出了一个函数的上界和下界。当只有一个渐进上界时，使用Ο记号。下面给出Ο(g(n))的定义：
Ο(g(n)) = {f(n)：存在正常量c，n0，使得对所有n ≥ n0，有0 ≤ f(n) ≤ c * g(n)}
图像表示如下：
Ω记号
正如Ο记号提供了一个函数的渐进上界一样，Ω记号提供了一个渐进下界。下面给出Ο(g(n))的定义：
Ω(g(n)) = {f(n)：存在正常量c，n0，使得对所有n ≥ n0，有0 ≤ c * g(n) ≤ f(n) }
图像表示如下：
ο记号
Ο记号提供的渐进上界可能是也可能不是渐进紧确的。因此我们使用ο记号来表示一个非紧确的渐进上界。定义如下：
ο(g(n)) = {f(n)：对于任意的正常量c，存在常量n0，使得对所有n ≥ n0，有0 ≤ f(n) < c * g(n)}
ω记号
同上，我们用ω记号来表示一个非紧确的渐进下界。形式化的定义是：
ω(g(n)) = {f(n)：对于任意的正常量c，存在常量n0，使得对所有n ≥ n0，有0 ≤ c * g(n) < f(n) }
等式和不等式中的渐进记号
- 对于形如2n²+3n+1 = 2n²+θ(n)的等式的解释是：2n²+3n+1 = 2n²+f(n)，f(n) = θ(n)（f(n) ∈ θ(n)）。
- 对于形如 2n² + θ(n) = θ(n²)的等式的解释是：无论怎样选择等号左边的匿名函数，总有办法开选择等号右边的匿名函数来使等式成立。