3.1 一些符号

• o 相当于
• 渐近上界O 相当于
  
• 渐近紧界相当于
  
• 渐近下界相当于
  
• 相当于
• 传递性
• 自反性
• 对称性
• 反对称性

3.2 递归式的复杂度

递归式的复杂度一定是指数，如2n

例1：

例2：选C

3.3 用主方法求解递归式

令和是常数，是一个函数，是定义在非负整数上的递归式

其中我们将解释为或，那么有如下渐近界：

1. 若对某个常数有，则。
2. 若，则。
3. 若对某个常数有，且对某个常数和所有足够大的
   有，则

例：