复杂度表示
大O表示法的定义(Bachmann–Landau Notations)
已知时间函数 f,g: \mathbb{N} \to \mathbb{R}, 则
- 渐进上限: f=O(g) \iff \exists c>0, \exists N, \forall n\geq N, f(n)\leq c\cdot g(n)
- 渐进下限: f=\Omega(g) \iff \exists c>0, \exists N, \forall n\geq N, f(n)\geq c\cdot g(n)
- 渐进约束: f=\Theta(g) \iff \exists c_1,c_2>0, \exists N, \forall n\geq N, c_1\cdot g(n)\leq f(n)\leq c_2\cdot g(n)
- 严格小于: f=o(g) \iff \forall c>0, \exists N, \forall n\geq N, f(n)< c\cdot g(n)
- 严格大于: f=\omega(g) \iff \forall c>0, \exists N, \forall n\geq N, f(n)> c\cdot g(n)
- 严格相等: f=\theta(g) \iff f\sim g \iff \lim_{n\to\infty}\frac{f(n)}{g(n)}=1
大O表示法的性质
- f=O(g)\iff k\cdot f=O(g)
- f_1=O(g_1) \land f_2=O(g_2) \implies f_1+f_2=O(\max(g_1,g_2))
- f_1=O(g_1) \land f_2=O(g_2) \implies f_1\cdot f_2=O(g_1\cdot g_2)
上述命题的证明:
- f=O(g) \iff \exists c>0, \exists N, \forall n\geq N, f(n)\leq c\cdot g(n)
\iff \exists N, \forall n\geq N, (k\cdot f)(n)\leq (k\cdot c)\cdot g(n) \iff k\cdot f=O(g)
- f_1=O(g_1) \land f_2=O(g_2) \iff
\exists c_1,c_2>0, \exists N_1,N_2, [\forall n\geq N_1, f_1(n)\leq c_1\cdot g_1(n)]\land[\forall n\geq N_2, f_2(n)\leq c_2\cdot g_2(n)]
\implies \forall n\geq\max(N_1,N_2), f_1(n)+f_2(n)\leq c_1\cdot g_1(n)+c_2\cdot g_2(n)\leq 2\max(c_1,c_2)\cdot\max(g_1(n),g_2(n))
\implies f_1+f_2=O(\max(g_1,g_2))
- f_1=O(g_1) \land f_2=O(g_2) \iff
\exists c_1,c_2>0, \exists N_1,N_2, [\forall n\geq N_1, f_1(n)\leq c_1\cdot g_1(n)]\land[\forall n\geq N_2, f_2(n)\leq c_2\cdot g_2(n)]
\implies \forall n\geq\max(N_1,N_2), f_1(n)\cdot f_2(n)\leq c_1\cdot g_1(n)\cdot c_2\cdot g_2(n)\leq (c_1\cdot c_2)\cdot g_1(n)\cdot g_2(n)
\implies f_1\cdot f_2=O(g_1\cdot g_2)
| 英文名 | 大O表示法 | 中文名 |
|---|
| Constant | O(1) | 常数 |
| Double Logarithimic | O(\log\log n) | 双重对数 |
| Logarithimic | O(\log n) | 对数 |
| Polylogarithimic | O((\log n)^c) | 多对数 |
| Fractional Power | O(n^c), c\in(0,1) | 分数幂 |
| Linear | O(n) | 线性 |
| Linearithmic | O(n\log n) | 对数线性 |
| Quadratic | O(n^2) | 平方 |
| Polynomial | O(n^c) | 多项式 |
| Exponential | O(c^n) | 指数 |
| Factorial | O(n!) | 阶乘 |
n!=\sqrt{2\pi n}\cdot(n/e)^n\cdot[1+O(1/n)]
[1\sim n^{1/\lg n}]<\lg(\lg^*n)<\lg^*n<\lg^*(\lg n)<2^{\lg^*n}<\ln\ln n<\sqrt{\lg n}<\ln n<\lg^2 n
<2^{\sqrt{2\lg n}}<[\sqrt{n}=(\sqrt{2})^{\lg n}=2^{1/2\lg n}]<[n=2^{\lg n}]<\lg(n!)\sim n\lg n
<[n^2=4^{\lg n}]<n^3<(\lg n)!<[n^{\lg\lg n}\sim(\lg n)^{\lg n}]
<(3/2)^n<2^n<n\cdot2^n<e^n<n!<(n+1)!<2^{2^n}<2^{2^{n+1}}