有关函数渐近的界的定理

定理1

设 是定义域为自然数集合的函数.

1. 如果 存在，并且等于某个常数 ，那么.
2. 如果，那么.
3. 如果，那么.

定理2

设函数 的定义域为自然数集合，

1. 如果 且 ，那么 .

2. 如果 且 ，那么 .

3. 如果 且 ，那么 .

定理3

假设函数 的定义域为自然数集，若对某个其它函数 , 有 和 ，那么

小结

估计函数的阶的方法：

• 计算极限

• 阶具有传递性

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

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