大O记号定义:对函数f(x)与g(x),”f(x)是O(g(x))的”等价于“存在一对数C和k,使x > k时,恒有‘|f(x)| <= C|g(x)|’”。此处的C和k被称作这个关系的凭证

两个典型证明模式:

  • 证明f(x)是O(g(x))的:证明存在一对数C、k,使定义中的关系成立。
  • 证明f(x)不是O(g(x))的:一般使用反证,先假设存在一个C、k数对,之后一定能推出来与假设矛盾。

只要找到一对有效的C、k,则对给定的大O关系,有无数对C和k满足这个大O关系。(因为比那个有效的C、k更大的数对一定可以满足给定的大O关系)

如果f(x)和g(x)都是O(h(x))的,则说f(x)和g(x)同阶。

部分重要函数的大O估计:

  • n次多项式:O( x ^ n )
  • n个正数之和:O( x ^ 2 )
  • 阶乘:O( nlogn )

函数关系的大O排序:

1 < logn < n < nlogn < exp( n, 2 ) < exp( 2, n ) < factorial(n)

大O关系的运算法则:

  • ( f1 + f2 )(x) is O( max( g1(x), g2(x) ) )
  • (f1 • f2)(x) is O( g1(x)g2(x) )

大Ω定义:(将大O定义中,>= Cg(x)改成<= Cg(x)即可)

大O和大Ω的关系:f(x) is O( g(x) ) if and only if g(x) is Ω(f(x)).

大Θ定义:f(x) is Θ(g(x)) if f(x) is O(g(x)) and f(x) is Ω(g(x)). 此时,f(x)也是与g(x)同阶的。

两个函数的大Θ关系是对称的。

“f(x)是Θ(g(x)) 的”等价于“存在C1、C2、k,使x > k时恒有C1|g(x)| <= f(x) <= C2|g(x)|”。