有关函数渐近的界的定理
定理1
设 f,g 是定义域为自然数集合的函数.
- 如果n→+∞limg(n)f(n) 存在,并且等于某个常数 c>0 ,那么f(n)=Θ(g(n)).
- 如果n→+∞limg(n)f(n)=0,那么f(n)=o(g(n)).
- 如果n→+∞limg(n)f(n)=+∞,那么f(n)=ω(g(n)).
定理2
设函数 f,g,h 的定义域为自然数集合,
-
如果 f=O(g) 且 g=O(h),那么 f=O(h).
-
如果 f=Ω(g) 且 g=Ω(h),那么 f=Ω(h).
-
如果 f=Θ(g) 且 g=Θ(h),那么 f=Θ(h).
定理3
假设函数 f,g 的定义域为自然数集,若对某个其它函数 h, 有 f=O(h) 和 g=O(h),那么f+g=O(h)
小结
估计函数的阶的方法:
算法的时间复杂度是各步操作时间之和,在常数步的情况下取最高阶的函数即可.