背景
讲述了三种方法来推导出递归式
代换法(数学归纳法)
递归树
主方法
代换法
代换法分如下两步
- 猜测解的形式
- 数学归纳法找出解的正确有效常数
递归树
画一个递归树，每个节点都表示递归函数调用集合中额一个子问题的代价；把每一层代价相加得到每一层代价的集合，再把每层代价相加，得到所有层次的总代价。递归式表示分治算法的运行时间的时候，递归树的方法效果更加明显。
主方法
先看下主定律的定义：令a≥1和b>1是常数，f(n)是一个函数，T(n)是定义在非负整数上的递归式 T(n) = aT(n/b) + f(n)。
这个也是我们推导出递归式的主要方法，代换法、递归树相对为辅助。
主定律a个子问题每个子问题的时间复杂度为T(n/b)，划分问题和合并子问题答案的代价为f(n)。
主定律公式包含三种条件，并非对所有的f(n)都成立。仅当满足次三类条件的才能使用主定律推导。
版权声明：本文为博主原创文章，未经允许不得转载。