渐进分析符号

$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 (g(n))$$