有关函数渐近的界的定理

定理1

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

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

定理2

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

  1. 如果 f=O(g)f=O(g)g=O(h)g=O(h),那么 f=O(h)f=O(h).

  2. 如果 f=Ω(g)f=Ω(g)g=Ω(h)g=Ω(h),那么 f=Ω(h)f=Ω(h).

  3. 如果 f=Θ(g)f=Θ(g)g=Θ(h)g=Θ(h),那么 f=Θ(h)f=Θ(h).

定理3

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

小结

估计函数的阶的方法:

  • 计算极限

  • 阶具有传递性

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

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