算法导论二-递归

一，递归式
递归算法是采用分治的方法，把一个“大问题”分解出若干个相似的“小问题”求解。
二，代换法解递归

利用数学归纳法证明递归式的时间复杂度是否符合上界或下界。
步骤1: 根据递归式猜解
步骤2: 数学归纳验证
由于步骤1 是比较麻烦的, 并且需要经验. 所以代换法常用来做验证, 喝下面的递归树法配合使用. 通过递归树得出解. 然后使用代换法进行验证.
例子: T(n) = 4(n/2) + n . 渐近上界: O(n³) 和 O(n²).
三，递归树法解递归
在递归树中，每一个结点都代表一个子代价，每层的代价是该层所有子代价的总和，总问题的代价就是所有层的代价总和。所以，我们利用递归树求解代价，需要知道，一个是每一层的代价，一个是树的高度。
如图：可得最终解为： Θ（n）= n²。
例子. T(n) = T(n/2)+T(n/4)+n²

四，主定理法解递归

主方法为如下形式的递归式提供了一种“菜谱”式的求解方法:
T(n)=aT(n/b)+f(n)
其中a≥1和b>1是常数，f(n)是渐近正函数.
这个递推式将规模为n的问题分解为a个子问题，每个子问题的规模为n/b，a个子问题递归地求解，每个花费时间T(n/b)。函数f(n)包含了问题分解和子问题解合并的代价。同样，这个递归式也没有考虑上取整、下取整、边界条件等，结果不会影响递归式的渐近性质。
有如下规则 <不满足规则的使用上面的方法解>
主定理的证明 :

1，整个递归树的权重从根节点到叶节点一直增加，所以整个递归树的权重主要在叶子节点上；

2，(k = 0)递归树每层的权重大致相同，总共h层，所以整个递归树的权重将各层的权重加起来即可；

3，则与CASE 1的情况正好相反，所以整个递归树的权重主要在根节点上。