1.2 如何看待《算法导论》

liweiwei1419 ... 2021-12-7 About 8 min

说明

本文来自我于 2021 年 8 月 2 日 发送的公众号文章 我如何看待《算法导论》和《算法》 (opens new window)

今天要和大家分享的话题是如何看《算法(第 4 版)》和《算法导论(第 3 版)》。

《算法导论(第 3 版)》我也不知道是从哪儿听说的,名气很大,看到的比较多的观点是:不适合新手朋友(我基本同意)。《算法(第 4 版)》是我在知乎上看到别人推荐的,这本书对我的帮助很大。

先说重点

  • 我的分享很主观,仅供参考,欢迎讨论;
  • 我没有承接任何商业推广,只是作为《算法图解》《算法(第 4 版)》《算法导论》的读者写一点读后感;
  • 《算法图解》是我为了买《算法(第 4 版)》拼单凑的一本书,恰好它比较有趣,适合入门,所以没有必要买这本书;
  • 《算法(第 4 版)》《算法导论》不是刷题的书,没有讲「二分查找」的几种写法它们的区别和联系、没有讲「滑动窗口」「双指针」,甚至都没有介绍「二叉树的前、中、后序遍历」,即使《算法导论(第 3 版)》有介绍「动态规划」,「动态规划」没有讲「无后效性」,没有讲「求解的过程构成了有向无环图」,看了对做题帮助也不大,没有讲「回溯算法」;
  • 如果只是想通过面试题,就直接去做面试题,看题解,总结题型和思路,自己的思考和练习很重要,不看这些经典的书关系不大。或者学习到了哪些知识点不太懂的,再去翻这两本书看一看;
  • 《算法(第 4 版)》《算法导论》它们是非常经典的书籍,里面讲的是「算法很好玩」的事情,讲的是思想,如果你真的对算法与数据结构很感兴趣,我是很推荐看这两本书的,并且反复阅读、推敲。在《算法(第 4 版)》的致谢中是这样说的:「本书的编写花了近 40 年时间」,它是经过时间沉淀和检验的,并且《算法(第 4 版)》本身就是一本(普林斯顿大学)教材。所以很多介绍「算法与数据结构」的教材大部分都会参考它们或者其中之一,那我们倒不如直接看这两本书,找到自己需要的部分学习就好。

现在开始嘚吧嘚:

《算法导论(第 3 版)》我很早就买了,我同学推荐的,在我还没有学习算法的时候,当时因为没有学习算法与数据结构的动力,所以根本看不进去。

我真的开始下定决心学习算法与数据结构是在 2017 年 5 月,当时买了两本书,一本是《算法图解》,另一本就是《算法(第 4 版)》。

# 1. 《算法图解》:入门书籍之一

《算法图解》这本书现在看来,从知识点的角度来说,其实它是不够的,但是它的确是带我入门的一本书,这本书比较薄,有很多漫画,一节的内容不是很多,很快能够看完。现在翻一翻都能够发现里面讲错的地方。

《算法图解》

  • 优点:很薄,漫画和故事比起文字描述更形象,能够建立对一些算法与数据结构的基本认识;
  • 缺点:内容太少,各个章节之间是独立的,不能够形成完整的知识体系。

# 2.《算法(第 4 版)》:真正入门书籍

我真正入门是从《算法(第 4 版)》这本书开始的。

这本书给我的感觉是:纸张很白、摸起来很舒服。书本的最前面是红、黑双色印刷的彩图,给我的感觉是「很专业」。

我从第 2 章「排序」开始看起的「选择排序」「插入排序」「归并排序」「快速排序」然后是「优先队列」。排序算法是我最早接触的算法。以前使用排序只知道 Arrays.sort()

《算法(第 4 版)》关于排序算法讲得非常详细,总结了各种排序算法的优缺点。

例如,「选择排序」的特点是:

「插入排序」应用在「部分有序」的数组上很有效:

比较「选择排序」和「插入排序」可以通过「调试」「分析」「猜想」「验证」的步骤。

猜想 -> 验证」这样的思想贯穿在这一章节。有了想法,就需要通过实验来验证。

「归并排序」和「快速排序」的部分是所有讲解「归并排序」和「快速排序」的教程里最好的,没有之一

在每一节的后面有「答疑」「练习」「提高」「实验题」,可以丰富我们对知识点的认识。

《算法(第 4 版)》和《算法导论(第 3 版)》里很多的知识点是通过「思考题」和「练习」的形式给出的。

这本书我感觉最好的地方在于做到了 算法知识点的讲解循序渐进,会介绍这些算法与数据结构是怎么来的,应用在什么地方。厚厚的一本书,知识点很密集。

第 3 章「查找」介绍了「二叉搜索树」「平衡二叉树」「散列表」,这三个数据结构是除了「栈」和「队列」以外最主要的、非常重要的复杂的数据结构。

在「平衡二叉树」的一开始介绍了「2-3 查找树」,其实就是让「二叉搜索树」的每一个结点承载了更多的信息。理解「2-3 查找树」是理解「红黑树」的基础

《算法(第 4 版)》介绍的这些内容我认为是绝大多数工程向的程序员需要知道的算法基础知识

第 4 章「图」,除了介绍「深度优先搜索」和「广度优先搜索」以外,还介绍了「带权图」中的两个最常见的算法:「最小生成树」和「单源最短路径」。

  • 「最小生成树」的一开始会介绍「切分定理」,然后才开始讲解 Prim 算法和 Kruskal 算法;
  • 「单源最短路径」的一开始会介绍「松弛操作」,然后介绍 Dijkstra 算法。

这本书虽然没有介绍「动态规划」和「贪心算法」,其实「单源最短路径」的知识就应用了「动态规划」和「贪心算法」的思想。

第 5 章「字符串」我看得比较少,有介绍 KMP 算法,但我觉得 KMP 算法讲得比较好的是《算法导论》。

# 3.《算法导论(第 3 版)》:不是一点都看不懂

有一说一,这本书阅读起来不是很轻松。我和朋友聊过,绝大多数朋友都觉得《算法导论(第 3 版)》不适合初学者,我认可。因为我在一点都不懂的时候翻这本书真的一点都没有看进去。这是因为 我不知道这本书里哪些东西是我需要的

我阅读了《算法(第 4 版)》以后,并且在「力扣」上已经做了一些问题以后。这个时候我已经有了一些算法基础,再看《算法导论(第 3 版)》,其实就好多了。因为有一些内容其实是重合的,还有一些内容是 现阶段 我根本不需要的(也许根本用不到)。

下面罗列一些我从《算法导论(第 3 版)》这本书上学到的有用的知识:

  • 循环不变式:用于证明算法的有效性,这本书后面的很多知识点都用「循环不变量」给出了解释,只要看到「初始化」「保持」「终止」这三个黑体字的时候,就是在应用「循环不变式」;
  • 时间复杂度的极限定义,用极限定义来解释时间复杂度,我认为是准确的。所以我在和大家介绍时间复杂度的概念的时候,都会拿出极限的定义,才能解释清楚为什么「常数系数可以看成 1 」「常数加法项可以忽略」「低次项忽略,保留最高次项」;
  • 主定理:用于求解「递归」函数的时间复杂度的工具;
  • 分治算法:「递归」与「分治」不分家。介绍了「递归」的三个步骤:「分解」「解决」「合并」。并且介绍了递归算法的时间复杂度计算工具:主定理;
  • 堆排序、快速排序、散列表、二叉搜索树、红黑树,这些在《算法(第 4 版)》里都讲过;
  • 贪心算法:我觉得「贪心算法」这部分是讲得很清楚的:「只做出当前看起来最好的部分」「贪心选择性质」,也提到了「最优子结构」。还比较了「递归贪心算法」和「迭代贪心算法」;
  • 字符串匹配,这部分要花点时间仔细看,做做笔记。

我也不想硬说《算法导论(第 3 版)》这本书有多好,我的结论依然是:它不会教你怎么做题,如果你真的对算法很感兴趣,它是一本很好的书籍。如果你真的需要了解并且深入算法知识,它值得仔细阅读,读你需要的部分。不要从头读到尾,没有目的的阅读。

Last update: January 20, 2022 01:47
Contributors: liweiwei1419 , suanfa8