3. 函数的增长

本章给出集中标准方法来简化算法的渐进分析。

渐进符号

Θ 渐进紧确界

   $f(n)=\Theta(g(n))$ 类似于 a = b
   当n>n0时，存在常数c₁和c₂使得c₁·g(n) <= f(n) <= c₂·g(n)

Ο 渐进上界

   $f(n)=O(g(n))$ 类似于 a ≤ b
   当n>n₀时，存在一个常数c使得 f(n) <= c·g(n)

Ω 渐进下界

   $f(n)=\Omega(g(n))$ 类似于 a ≥ b
   当n>n₀时，存在一个常数c使得 f(n) >= c·g(n)

ο

   $f(n)=\omicron(g(n))$ 类似于 a < b

ω

   $f(n)=\omega(g(n))$ 类似于 a > b

此图为书中截图，很好的说明了Θ Ο Ω 的含义