算法图解

2018-12-22 张子阳 推荐:

算法是编程的基础，每隔一段时间就应当重温一下。算法的书大多比较艰涩，可能花很久还在看前两章，然后因为什么事情就中断了（往往是被其他更有趣的书所吸引），最后就烂尾了，再次拿起已经不知道是什么时候了。这本书则简单的多，如同书名所述，这本书包含了大量图片，使得理解更加方便。

全书只有短短的180页，图片又占了很多的部分，因此只要三五天就可以一口气看完。而在这几天的时间内，可以从最简单的两分查找，一直学习到复杂的动态规划和K最近邻算法。当然，每种算法都是只提出了典型的情况，而不涉及难度更高的变体或者优化等。

书中并未给出所有算法的实现代码，但都给出了实现的思路或者图示，对于一些经典的问题，使用自己熟悉的语言（或者想要熟悉的语言）去实现一遍是学习的最好办法，书中使用的语言是Python。

算法和数据结构是密不可分的，书大体可以分为3部分，第1部分介绍了基本的数据结构：链表、数组、散列表，基本的几个算法：递归、两分查找、选择排序、快速排序。以及衡量算法运行时间的大O表示法。第2部分介绍了图及其相关的广度优先搜索和狄克斯特拉算法；第3部分讨论了识别NP完全问题以及贪婪算法，还介绍了动态规划和K最近邻算法。

读完这些之后，会有这样一个感受：那些听上去很复杂的算法，比如狄克斯特拉算法、贪婪算法、动态规划等，其实现原理并不复杂。

在书的最后一章，作者提出了更进一步学习的方向，包括反向索引（搜索引擎）、并行算法、线性规划等。

书中的部分算法实现，我也使用Go语言重写了部分，整理过后再贴出来吧：

1. 将循环改为递归实现
2. 快速排序
3. 广度优先搜索：最短路径
4. 广度优先搜索：查找关系网
5. 狄克斯特拉算法
6. 贪婪算法
7. 动态规划

感谢阅读，希望这篇文章能给你带来帮助！