- O符号，f(n) = O(g(n))，表示f(n)的复杂度最多与g(n)一个数量级，<=，渐近上界。
- Ω符号，f(n) = Ω(g(n))，f(n)的复杂度最少与g(n)一个数量级，>=，渐近下界。
- o符号，f(n) = o(g(n))，表示f(n)的复杂度要比g(n)的数量级小，<，非渐近紧缺上界。
- ω符号，f(n) = ω(g(n))，表示f(n)的复杂度要比g(n)的数量级大，>，非渐近紧缺下界。
- Θ符号，(n) = Θ(g(n))，表示f(n)的复杂度既大于等于g(n)的复杂度，又小于等于g(n)的复杂度，=，紧确界。
- 标记符号
- 单调性
- 取整：向上取整 ⌈n⌉，向下取整 ⌊n⌋
关系 x - 1 < ⌊n⌋ <= x <= ⌈n⌉ < x + 1
⌊n/2⌋ + ⌈n/2⌉ = n - 模运算：a mod n = a%n = a - n⌊a/n⌋
- 常用函数
- 多项式
- 指数：e^x = 1+x+1/2!x^2+...+1/n!x^n (麦克劳林公式)
- 对数：a^logbc = (b^logba)^logbc = c^logba, ln(1+x) = x-1/2x^2+1/3x^3-1/4*x^4.+((-1)^n)/n+1)x^(n+1) (麦克劳林公式)
- 阶乘：斯特林近似公式 1/(12n+1) < an < 1/12
- 多重函数
- 多重对数函数：lg*n只有在lg(i-1)n > 0时，lgin才有意义，特点：增长慢 (((a^n)^n)^n)，lg*(2^65536) = 5
- 斐波那契函数：f(i) = f(i-1) + f(i-2), i>=2, 于黄金分割率的关系
注解：本章知识依赖于高等数学的基础，所以快去看高数