[TOC]

递归形式的时间函数T(n)的解法

递推法

• 低阶项忽略不写，因为对增长速率没什么影响
• Θ(1)和C是等价的,Θ(n)和cn是等价的

• 为什么令n = 2的i次方?
• 不等于时，结果一样

更清晰的方法：递归树方法

• 更加复杂的问题也可以用递归树方法
• 没搞清楚？
  
  
• cn在这里是低阶项

• 大部分算法都有基本步骤
• Fib数包含重叠子问题，不适合分治法，可以考虑动态规划方法，贪心方法，
  他们是重叠越多，相对分治法越好

• 子问题的规模一个是下界，一个是..的上届，不一样，所以得分开写