渐进分析符号

$O$：渐进上界记号 （取最大也可以更大）（最复杂情况下的复杂度，最常见）

$\Omega$ ：渐进下界（最小，同时可以更小）

$\Theta$：渐进近界（等比的包络线）

例如：

$$f(n)=32n^2+17n+1$$

可以表示为

$$O(n^2),O(n^3),\Omega (n^2),\Omega (n),\Theta (n^2)$$ $$O(f)+O(g)=O(max(f,g))$$ $$O(f)O(g)=O(f\cdot g)$$

---

非紧上界：

$$\underset{n\to \infty }{\lim }\frac{f}{g}=0$$ $$o(g(n))$$

---

非紧下界：

$$\underset{n\to \infty }{\lim }\frac{f}{g}=\infty$$ $$\omega$$