算法导论学习笔记-第四章-递归式

时间:2022-05-30 22:10:12

第四章 递归式

 

总结:这一章讲了三种解递归式的方法,代换法、递归树方法、主方法。

 

1.    代换法

两个步骤:

1)    猜测解的形式

2)    用数学归纳法找出解真正有效的常数

 

2.    递归树

画出一颗递归树来得到好猜测。

在递归树中,每一个结点都代表递归函数调用集合中一个子问题的代价。我们将树中每一层内的代价相加得到一个每层代价的集合,再将每层的代价相加得到递归是所有层次的总代价。

 

3.    主方法

依赖主定理,要记忆三种情况