大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)|”。