有关函数渐近的界的定理

定理1

设 $f,g$ 是定义域为自然数集合的函数.

1. 如果$\lim\limits_{n→+∞} \frac{f(n)}{g(n)}$ 存在，并且等于某个常数 $c>0$ ，那么$f(n)=Θ(g(n))$.
2. 如果$\lim\limits_{n→+∞} \frac{f(n)}{g(n)} =0$，那么$f(n)=o(g(n))$.
3. 如果$\lim\limits_{n→+∞} \frac{f(n)}{g(n)} =+∞$，那么$f(n)=ω(g(n))$.

定理2

设函数 $f,g,h$ 的定义域为自然数集合，

1. 如果 $f=O(g)$ 且 $g=O(h)$，那么 $f=O(h)$.

2. 如果 $f=Ω(g)$ 且 $g=Ω(h)$，那么 $f=Ω(h)$.

3. 如果 $f=Θ(g)$ 且 $g=Θ(h)$，那么 $f=Θ(h)$.

定理3

假设函数 $f,g$ 的定义域为自然数集，若对某个其它函数 $h$, 有 $f=O(h)$ 和 $g=O(h)$，那么$f+g=O(h)$

小结

估计函数的阶的方法：

• 计算极限

• 阶具有传递性

• 对数函数的阶 < 幂函数的阶，多项式函数的阶 < 指数函数的阶.

算法的时间复杂度是各步操作时间之和，在常数步的情况下取最高阶的函数即可.