《算法概论》读后感800字

其实更像是《算法评注》。能看到不少别的教材没讲过的内容，讲过的也会尝试用新的角度来描述，譬如说：分治法里讲大数乘法，矩阵乘法和快速傅里叶变换。我没有读过《算法导论》但是我刚刚查证了一下，矩阵乘法出现在《算法导论》分治法的章节附注中，快速傅里叶变换完全没有发现踪影。

讲分治法讲这几个例子也独出心裁。一是因为这几个例子确实在实践中比较重要，但是教材不太爱讲。二是这几个例子中，原问题不是被分成两个子问题，而是四个、八个子问题。这对分治法通常都是分成两半来考虑的人们相当有启发。“把四个子问题转化为三个子问题就能优化复杂度”，只有两个子问题时完全不会考虑这层。

动态规划和DAG的关系。本书提出了动态规划都隐含着DAG的想法，并把最短编辑距离转化为相应DAG的最短路径，最长递增子序列转化为相应DAG的最长距离。这个观点确实令人惊讶，也确实有道理——所有问题都能由子问题求解，这个过程是单向的，当然不会产生环。

这个想法对于动态规划的问题可能帮助不大，因为动态规划的类型很多，甚至最后求解的方法也未必是查询dp数组的某一项。譬如最长递增子序列还有一种定义子问题的方式：dp[i]:=min{长度为i的递增子序列的结尾}。这类dp问题最后都要遍历一边dp数组确定解在哪里，和定义某个DAG似乎相去甚远。

但是可能这对DAG的问题帮助就大了，意外着DAG的一些问题是可以用动态规划做的，事实上单源最短路径的计算、多源最短路径的计算也确实都可以从动态规划来讲。

一个超有趣的介绍：图上两点的最短距离可以构造一个物理系统来模拟。每个节点对应一个球，边用一个没有弹性的绳子表示。用手向两边拉源点和汇点，拉成直线时的路径就是最短距离的路径。这很像是一些代数问题的几何证明，非常巧妙。也不禁让人思考物理系统和计算机系统是否能构造出某种对应。

书中还提到了最优化问题和搜索问题的互相归约。这个议题也是少见的，甚至很少有人专门区分最优化和搜索问题。在网上能搜到MIT和UCSD两门课的讲义里提到了这个，我想这两门课的教授和本书作者应该也是同一类型吧哈哈哈。

甚至这本十几年前的书的最后提了量子算法！即使现在的教材我也没见过涉及量子算法的。可以看出本书是一本多么令人大开眼界的作品了，极其适合做某本全面教材的辅助课外读物。