有关函数渐近的界的定理

定理3

定理 假设函数f 和g的定义域为自然数集，若对某个其它函数 h, 有 f =O(h) 和 g=O(h)，
那么 f + g = O(h).
该性质可以推广到有限个函数.

算法由有限步骤构成. 若每一步的时间复杂度函数的上界都是 h(n)，那么该算法的时间复杂度函数可以写作 O(h(n)).

小结

• 估计函数的阶的方法：
计算极限
阶具有传递性
• 对数函数的阶低于幂函数的阶，多项
式函数的阶低于指数函数的阶

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

几类重要的函数

小结

• 几类常用函数的阶的性质

• 对数函数
• 指数函数
• 阶乘函数
• 取整函数

• 如何利用上述性质估计函数的阶？