[TOC]

• 不同算法循环不变式不同

1. 什么叫循环不变式？
   
   

第二章 渐进符号

2.1

等号的意思是说2边的函数增长速率相同，而不是绝对值相等

2.2 O符号

紧上界：对于例4，n是f(n)的上届，找不到比n更小的f(n)的上届
松上界：对于例5,实际上f(n)的上界没那么大，还可以小
o符号只能表示松上界

2.3 符号

• 第一个符号等式两边的函数可以交换，第二个第三个符号不支持这种交换
• o不能表示紧下界？[15：05]

  2.4和定理3.1

  
• 难以确定函数之间的增长速度关系用上面这种极限的方法
• 上图中f(n) < g(n)是说f(n)比g(n)增长得要慢
  
  

  第三章 分治法及递归算法的分析方法

  3.1 分治法

  
  
  
• 函数调用的时间在具体的机器上是常数
  
• 无穷大的作用是哨兵
• 递归算法怎么来计算他的时间复杂度？
  
• T(N) = An + B = θ(n) 这里严格来讲是O(n)
• n <= C中的C具体到归并排序算法来 就是递归终止条件n=1，子数组只包含一个函数
  
• 消除递归形式的时间复杂度T(n)