书评《算法导论》

article/2025/10/19 21:09:46

在这里插入图片描述

最近空闲时间在看《算法导论》。由于之前有数据结构与算法的基础，并且也写过几百道代码题。所以现在看这本书反而有了一些更深的感悟。

《算法导论》确实不适合初学者，尤其是不适合实践派。对于实践派，《数据结构与算法分析——C语言描述》、邓俊辉老师的《数据结构》，《算法》红皮书无疑都是很好的上手教程。我读《算法导论》，是把它当作一本数学书来读的，其中很多篇幅关注于算法设计、正确性证明、算法分析。

《算法导论》之于“实践派算法书籍”，就像是《数学分析》之于《高等数学》。初上手的算法书教大家如何去开车，《算法导论》则是教大家如何去造车。

举个例子：

第15章动态规划和第16章贪心算法。
这本书难能可贵的地方在于把动态规划和贪心算法的问题范式给讲清楚了。也即当问题出现“最优子结构+子问题重叠”时适合用动态规划，当问题出现“最优子结构+贪心选择正确”时适合用贪心算法。其实分治算法也可以包括进来，即“最优子结构+没有子问题重叠”。
这些原理非常宝贵，在我之前刷题时，更多是靠“智商”去“感觉”这个题适合用动态规划还是贪心算法，这种思维模式很“野”，缺乏正规的一招一式。遇到复杂问题时如果猜不出来用什么算法，则会变得束手无策。我的这个问题在大三的时候，就曾有一个室友指出来过。现在想来，他说的非常对。《算法导论》像是一个正确的老师，把我这种野路子出来的人带到正途上，从而经受正规的思维训练。
第24章单源最短路径。
这一章采用了定理——证明的方式进行描写，这种写法非常扎实。很多定理（例如这一章提到的“上届性质”和“收敛性质”）直觉上非常正确，会有一种“这明显正确啊，这还用证”的感觉。
对于学习、使用算法，这些证明确实没什么帮助。但是对于构建严谨的逻辑思维，这些证明都非常有必要。就像是为什么数学分析要证明根号2是无理数一样。有了这些证明，我们可以大胆地使用Dijkstra算法，并说出为什么Dijkstra算法不能带有负边，负边违背了正确性证明中的哪一步，为什么Bellman-Ford算法正确。
第17章摊还分析。
续上面的第2点。“直觉”帮助我们找到正确结论的方向，“形式化证明”帮助我们验证这些结论。我们不能过度依赖直觉去说明一个算法work与否。例如第17章思考题17-5自组织列表的竞争分析。这个移至前端策略也是分页、缓存中常用的LRU的理论基础。移至前端策略就是和最优策略的代价在数量级上是一样好的（4-competitive）？
你信吗？你若不信看我用摊还分析给你证明出来。
它符合直觉吗？这个时候才会发现证明的扎实性。我们不能过度依赖直觉去验证正确与否。一定要严格进行论证。
第5章概率分析和随机算法。
这一章最大的贡献是把“概率分析”和“随机算法”分清楚了。概率分析是在输入具有分布时的期望分析。随机算法则是在固定输入下算法本身产生随机的操作，目的通常是达到某种期望的时间界。