内容

• 主要内容是复杂度分析
• 大O标记
• 计算大O时的一般法则
  • 对数规律的一般法则
    如果一个算法用常数时间（O(1)）将问题的大小削减为其一部分（通常是1/2），那么该算法就是O(logN)的。

例子

1. 二分搜索提供了O(logN)的查找算法
2. 最大公因数的欧几里得算法也是O(logN)的
3. 幂运算的递归算法