第四章 递归式
总结:这一章讲了三种解递归式的方法,代换法、递归树方法、主方法。
1. 代换法
两个步骤:
1) 猜测解的形式
2) 用数学归纳法找出解真正有效的常数
2. 递归树
画出一颗递归树来得到好猜测。
在递归树中,每一个结点都代表递归函数调用集合中一个子问题的代价。我们将树中每一层内的代价相加得到一个每层代价的集合,再将每层的代价相加得到递归是所有层次的总代价。
3. 主方法
依赖主定理,要记忆三种情况
第四章 递归式
总结:这一章讲了三种解递归式的方法,代换法、递归树方法、主方法。
1. 代换法
两个步骤:
1) 猜测解的形式
2) 用数学归纳法找出解真正有效的常数
2. 递归树
画出一颗递归树来得到好猜测。
在递归树中,每一个结点都代表递归函数调用集合中一个子问题的代价。我们将树中每一层内的代价相加得到一个每层代价的集合,再将每层的代价相加得到递归是所有层次的总代价。
3. 主方法
依赖主定理,要记忆三种情况