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