渐进记号
五种渐进记号
- 大$O$记号：
对于给定函数$g(n)$，$f(n)=O(g(n))$：存在正常量 $c$ 和 $n_{0}$，使得对所有 $n \geq n_{0}$，有 $0 \leq f(n) \leq cg(n)$成立。$f(n)$ 只有一个渐进上界，$f(n)$ 的阶不高于 $g(n)$ 的阶。
- $\Omega$记号：
对于给定函数$g(n)$，$f(n)=O(g(n))$：存在正常量 $c$ 和 $n_{0}$，使得对所有 $n \geq n_{0}$，有 $0 \leq cg(n) \leq f(n)$成立。$f(n)$ 只有一个渐进下界，$f(n)$ 的阶不低于 $g(n)$ 的阶。
- $\Theta$记号：
对于给定函数 $g(n)$，$f(n)=\Theta(g(n))$：存在正常量 $c_{1}$，$c_{2}$ 和 $n_{0}$，使得对所有 $n \geq n_{0}$，有$0 \leq c_{1}g(n) \leq f(n) \leq c_{2}g(n)$ 成立。$\Theta$记号渐进地给出了一个函数的上界和下界，$f(n)$ 的阶等于 $g(n)$ 的阶
若$f(n)=O(g(n))$ 且 $f(n)= \Omega (g(n))$，则 $f(n)= \Theta (g(n))$。
- 小$o$记号：
对于给定函数$g(n)$，$f(n)=O(g(n))$：存在正常量 $c > 0$ 和 $n_{0} > 0$，使得对所有$n \geq n_{0}$，有$0 \leq f(n) < cg(n)$ 成立。$f(n)$ 只有一个渐进紧确上界，$f(n)$ 的阶低于 $g(n)$ 的阶。
- $\omega$记号：
对于给定函数 $g(n)$，$f(n)=O(g(n))$：存在正常量 $c > 0$ 和 $n_{0} > 0$，使得对所有 $n \geq n_{0}$，有$0 \leq cg(n) < f(n)$ 成立。$f(n)$ 只有一个渐进紧确下界，$f(n)$ 的阶高于 $g(n)$ 的阶。
相关定理
- 定理1：
（1）如果 $\lim_{n \to + \infty} \frac{f(n)}{g(n)}$存在，且为某个常数 $c$，则 $f(n)= \Theta (g(n))$
（2）如果$\lim_{n \to +\infty} \frac{f(n)}{g(n)}=0$，则$f(n)= O (g(n))$
（3）如果$lim_{n \to +\infty} \frac{f(n)}{g(n)}=\infty$，则$f(n)= \omega (g(n))$
由定理1可以导出两个重要结果：
(1)多项式函数的阶低于指数函数的阶：
$$n^{d}=o(r^{n}), \quad r > 1,d > 0$$
(2)对数函数的阶低于幂函数的阶：
$${\rm \ln}n=o(n^{d}), \quad d>0$$
- 定理2，传递性：
若$f(n)= \Theta (g(n))$，且$g(n)=\Theta (h(n))$，则$f(n)=\Theta(h(n))$。对于大$O$、小$o$、$\Omega$、$\omega$同样成立。
- 定理3：
$$f=O(h), \quad g=O(h) \rightarrow f+g=O(h)$$ 该性质可推广到有限个函数。算法由有限个步骤构成，若每一步的时间复杂度函数的上界都是$h(n)$，那么算法的时间复杂度函数可以写作$O(h(n))$
相关性质
- 1、自反性：
$$f(n)=\Theta (f(n))$$
$$f(n)=O(f(n))$$
$$f(n)=\Omega(f(n))$$
- 2、对称性：
$f(n)=\Theta(g(n))$，当且仅当$g(n)=\Theta(f(n))$
- 3、转置对称性：
$f(n)=O(g(n))$当且仅当$g(n)=\Omega(f(n))$ $f(n)=o(g(n))$当且仅当$g(n)=\omega(f(n))$
几类重要函数
- 至少指数函数级： $2^{n}$, $3^{n}$, $n!$, $2^{2^{n}}$, $n2^{n}$, $(\log n)^{\log n}=n^{\log \log n}$
- 多项式级： $n$, $n^{2}$, $n {\rm \log}n$, $n^{\frac{1}{2}}$, $n^{3}$, ${\rm \log}(n!)=\Theta(n {\rm \log}n)$
- 对数多项式级： ${\rm \log}n$, ${\rm \log}^{2}n$, ${\rm \log \log}n$, $\sqrt{\log n}$
取整函数
- $\lfloor x \rfloor$：向下取整，$\lceil x \rceil$：向上取整
- 一些性质：
$$x-1< \lfloor x \rfloor \leq x \leq \lceil x \rceil< x+1$$
$$\lfloor x+n \rfloor=\lfloor x \rfloor + n, \lceil x+n \rceil = \lceil x \rceil+ n$$
$$\left \lceil \frac{n}{2} \right \rceil + \left \lfloor \frac{n}{2} \right \rfloor= n$$
$$\left \lceil \frac{\left \lceil \frac{n}{a} \right \rceil}{b} \right \rceil = \left \lceil \frac{n}{a b} \right \rceil, \quad \left \lfloor \frac{\left \lfloor \frac{n}{a} \right \rfloor}{b} \right \rfloor = \left \lfloor \frac{n}{a b} \right \rfloor$$
参考资料
- 《算法导论》
- 《算法设计与分析》慕课