概述
本书共包含11章内容,不过第一章更像是引言(标题就叫"算法入门"),最后一章则主要介绍后续可以(也应该)学习的内容,以及本书未完全涵盖的主题(如MapReduce、布隆过滤器、SHA算法等)。那么本书具体包含哪些内容呢?让我们简单梳理一下。
首先,书中提到了算法复杂度和所谓的"大O表示法"。要知道绝大多数编程课程都只教授某些特定技能,却很少涉及算法执行时间复杂度和代码优化。
关于涉及的主题,我将在这个段落中快速概述。
开篇章节讲述了数组和链表,以及如何操作它们(包括排序和搜索)。列举了链表在读写速度和数据存储方面的优缺点。
接下来是递归的简短章节,涉及调用栈及其工作原理。
之后深入探讨了快速排序(采用"分治法")。为强化理解,作者提供了三个分治法的应用案例。讨论了基准元素的选择,并用图表比较了不同排序算法(包括前几章介绍的算法)的执行速度。
随后章节介绍了一种新的数据结构——哈希表。说明了适用场景(如去重、缓存、对象间关系建模等),并解释了哈希冲突的处理方法。
接着开始讲解图数据结构。虽然远不及我在"数学建模"课程中学到的深度,但至少涵盖了基本概念:图的定义、用途、应用场景,以及有向图与无向图的区别。既然图是关于"路径"的,相关算法包括广度优先搜索和最短路径查找。本章再次提到队列和栈,解释FIFO和LIFO原则(个人认为这部分应该放在前面章节)。值得注意的是,图结构占据了两章内容:第一章解决无权图的最短路径问题,第二章则通过Dijkstra算法解决带权图的最短路径问题。同样采用先理论后代码的示例讲解方式。关于包含负权边的Bellman-Ford算法,作者没有展开,留给读者自学。
最后部分探讨了日常编程中较少涉及的算法:贪心算法、NP完全问题的处理方法、将复杂问题分解为子问题的动态规划,以及机器学习中的K最近邻算法。
特色
书中配有辅助理解的示意图。每章包含5-7个实践性问题(部分含代码示例),书末提供参考答案。每章结尾还有4-5句话的"速查表"总结。
全书约300页,章节篇幅适中,读者很容易坚持读完。语言通俗易懂,阅读体验流畅。
总结
非常适合非科班出身的编程学习者。用浅显的语言讲解了各类排序搜索方法(二分查找、深度/广度优先搜索),重点解析了算法复杂度分析(大O表示法),甚至涵盖图论、最短路径算法、K最近邻等程序员必备的基础算法知识。