版本记录
| 版本号 | 时间 |
|---|---|
| V1.0 | 2017.08.16 |
前言
将数据结构和算法比作计算机的基石毫不为过，追求程序的高效是每一个软件工程师的梦想。下面就是我对算法方面的基础知识理论与实践的总结。感兴趣的可以看上面几篇。
1. 算法简单学习（一）—— 前言
2. 算法简单学习（二）—— 一个简单的插入排序
3. 算法简单学习（三）—— 分治法与合并排序
4. 算法简单学习（四）—— 冒泡排序
5. 算法简单学习（五）—— 函数的增长
6. 算法简单学习（六）—— 常用的几种相关函数
递归式
当一个算法包含对自身的递归调用时，其运行时间就可以用递归式(recurrence)表示、比如说：MERGE - SORT过程最坏情况运行时间T(n)可以由下式表示。
这个递归式的解我们已经知道，那就是T(n) = Θ(nlgn)。
这个递归式我们前面解答过，下面我们就系统的说下诸如此类的递归式的解法。递归式的解法主要有三种：
-
代换法
（substitution method）- 先猜有某个界存在，然后利用数学归纳法证明猜测的正确性。
-
递归树方法
（recursion - tree method）- 将递归式转化为树形结构，树中的结点代表在不同递归层次付出的代价，最后利用对和式限界的技术来解出递归式。
-
主方法
（master method）- 给出递归形式
T(n) = aT(n / b) + f(n)的界，其中a ≥ 1，b > 1, f(n)是给定的函数。
- 给出递归形式
这里还有一些细节要注意：
- 上取整和下取整的忽略
我们一般都假设自变量为整数，那么MERGE - SORT过程最坏情况运行时间T(n)实际上应该如下表示：
- 边界条件的忽略
为方便起见，常忽略递归式的边界条件，假设对小的n值T(n)是常量，例如，一般将递归式表示成：
T(n) = 2T(n / 2) + Θ(n)
并不明确给出当n很小时T(n)的值，原因在于，虽然递归式的解会随着T(1)的值的改变而改变，但是增长的阶没有变化。
综上：在表示和解递归式的时候，经常忽略上取整、下取整以及边界条件，进行分析时先假设没有这些细节，而后再确定他们重要与否，它们一般不重要，但是重要的是要知道它们在什么情况下是重要的。
代换法
代换方的步骤：
- 猜测解的形式。
- 用数学归纳法找出使解真正有效的常数。
但是代换法也有缺点：
- 边界条件不是很好处理。
- 递归式的解靠猜测，这无疑需要大量的经验做基础。不过猜测的时候，可以先证明递归式的较松的上下界，然后再缩小不确定性的区间。
递归树方法
这个方法其实就是，画一个递归树，每一个结点都代表递归函数调用集合中一个子问题的代价，我们将树中每一层内的代价相加得到一个每层代价的集合，再将每层的代价相加得到递归是所有层次的总代价，当用递归式表示分治算法的运行时间时，递归树的方法尤其有用。
下面我们就以T(n) = 3T(n / 4) + c n2为例，建立它的递归树。
图a中表示的是T(n)，图b中表示的是被扩展成一个等价的用来表示递归的树，根部cn2项表示递归在顶层时所花的代价。而根部以下的三棵字数表示这些n /4大小的子问题所需要的代价。 图c中展示了对图b做进一步处理的过程，对图b中代价为T(n / 4)的结点进行了扩展，三棵子树的根的代价分别是c(n / 4)2。
下面我们接着扩展。
图d展示的是，扩展了的递归树深度为log4n ，它有log4n + 1层。对于深度为i的结点，其子问题的大小为n / 4i，那么当n / 4i = 1，或是当i = log4n时子问题的大小可达到1，因此，这棵树有log4n + 1层。
下面给出这棵树总的代价表达式：
对于上式，利用无限递减等比级数作为上界，得到下面表达式。
下面我们在看另外一个递归表达式
T(n) = T(n / 3) + T(2n /3) + O(n)
直接给出其递归树。
可以证明树的深度是log3/2 n。
主方法
给出求解如下形式的递归式的食谱方法。
T(n) = aT(n / b) + f(n)
这里，a ≥ 1, b >1是常数，f(n)是一个渐近正的函数，主方法要求记忆三种情况。上面这个式子可以理解为：将规模为n的问题，划分为a个子问题的算法运行时间，每个子问题规模为 n / b， a和b均为常数，a个子问题被分别递归的解决，时间各为T(n / b)，划分原问题和合并答案的代价由函数f(n)描述。
主定理
下面我们就看一下主定理。
这里给出了三种情况，分别是在f(n)和nlogba进行比较下的结果。
下面看一个简单的例子：
T(n) = 9T(n / 3) + n
这里， a = 9, b = 3, f(n) = n，nlogba = Θ(n2)，对应于定理第一种情况，所以T(n) = Θ(n2)。
同样，你可以对下面式子应用定理。
T(n) = T(2n / 3) + 1
可以证明这个式子适用于定理的第二种情况，最后T(n) = Θ(lgn)。
后记
本篇主要讲述的就是递归式的三种解析方法，希望对大家有所帮助。
