算法导论

您所在的位置：网站首页 › 如何看懂算法导论 › 算法导论

算法导论

2024-07-17 11:22| 来源: 网络整理| 查看: 265

1. 利用数列知识

2. 替换法(代换法)

(1)猜测解-->数学归纳法证明；

(2)变量变换法；

3. 迭代法

(1)展开法；

(2)递归树法；

4. 主定理(主方法求解递推式)

5. 补充：递归与分治法(sch1)

递归设计技术

递归程序的非递归化

算法设计

（1）Fibonacci数

（2）生成全排列

（3）二分查找

（4）大整数乘法

（5）Strassen矩阵乘法

(6) 导线和开关(略)

1. 利用数列知识累加法：递推关系式为 $a_{n+1}-a_{n}=f(n))$ 采用累加法。累乘法：递推关系式为 $a_{n+1}/a_{n}=f(n)$ 采用累乘法。构造法：递推关系式为(1) $a_{n+1}=pa_{n}+q$ ，(2) $a_{n+1}=pa_{n}+q^{n}$ ，都可以通过恒等变形，构造出等差或等比数列，利用等差或等比数列的定义进行解题，其中的构造方法可通过待定系数法来进行。和化项法：递推公式为 $S_{n}=f(n)$ 或 $S_{n}=f(a_{n})$ 一般利用

5. 用特征方程求解递推方程（感觉比较生僻，不做解释）

6. 迭代法：从原始递推方程开始，反复将对于递推方程左边的函数用右边的等式代入，直到得到初值，然后将所得的结果进行化简。

例如在调用归并排序mergeSort(a,0,n-1)对数组a[0...n−1]排序时，执行时间T(n)的递推关系式为：

其中，O(n)为merge()所需要的时间，设为cn（c为正常量）。因此：

忽略求解细节。在我们求解递归式时，因为最终是要求得一个时间上限，所以在求解时常常省略一些细节。比如mergeSort(a,0,n-1)运行时间的实际递归式应该是：

但我们忽略这些上取整、下取整以及边界条件，甚至假设问题规模 $n=2^{k}$ ，这都是为方便求解而忽略的细节。经验和一些定理告诉我们，这些细节不会影响算法时间复杂度的渐近界。

类似的，我们也可以用迭代法求解汉诺塔递归求解时的时间复杂度。但遗憾的是，迭代法一般适用于一阶的递推方程。对于二阶及以上（即T(n)依赖它前面更多个递归项）的递推方程，迭代法将导致迭代后的项太多，从而使得求和公式过于复杂，因此需要将递推方程化简，利用差消法等技巧将高阶递推方程化为一阶递推方程。如在求快速排序算法平均时间复杂度T(n)的递推方程，T(n)依赖T(n−1)、T(n−2)、...、T(1)等所有的项，这样的递推方程也称为全部历史递推方程。（这里省略快速排序算法平均复杂度T(n)的求解过程）

小结：上面6种递推关系是高中、本科知识，在此重点介绍了迭代法，其它几种方法虽未在本篇中使用，但可以加深对递推式求解的认识。

2. 替换法(代换法) (1)猜测解-->数学归纳法证明；

代换法实质上就是数学归纳法，因此求递推式分为两步：

1.猜测解的形式；

2.用数学归纳法求出解中的常数，并证明解是正确的。

遗憾的是并不存在通用的方法来猜测递归式的正确解，需要凭借经验，偶尔还需要创造力。即使猜出了递归式解的渐近界，也有可能在数学归纳证明时莫名其妙的失败。正是由于该方法技术细节较为难掌握，因此这个方法不适合用来求解递归方程，反而比较适合作为其他方法检验手段。在此不做总结。可以翻阅《算法导论》进行学习。

实际使用的是归纳法，即根据直觉经验判断结果应该是什么，然后再归纳求解。先代入常量c，然后归纳得出这样的c存在。

(2)变量变换法； 3. 迭代法 (1)展开法； (2)递归树法；

递归树是一棵结点带权值的树。初始的递归树只有一个结点，它的权标记为T(n)；然后按照递归树的迭代规则不断进行迭代，每迭代一次递归树就增加一层，直到树中不再含有权值为函数的结点（即叶结点都为T(1)）。下面以递归方程

来讲述递归树的迭代规则。

在得到递归树后，将树中每层中的代价求和，得到每层代价，然后将所有层的代价求和，得到所有层次的递归调用的总代价。在上图(d)部分中，完全展开的递归树高度为lgn (树高为根结点到叶结点最长简单路径上边的数目)，所有递归树具有lgn+1层，所以总代价为cn∗(lgn+1)，所有时间复杂度为Θ(nlgn)。

总结：递归树模型求解递归方程，本质上就是迭代思想的应用，利用递归方程迭代展开过程构造对应的递归树，然后把每层的时间代价进行求和。不过递归树模型更直观，同时递归树也克服了二阶及更高阶递推方程不方便迭代展开的痛点。

递归树法不是那么精确，取决于你画递归树的精确度。用递归树来猜测上界，然后用上面的代换法来证明正确性。