张子阳的博客

首页 读书 技术 店铺 关于
张子阳的博客 首页 读书 技术 关于

算法图解

2018-12-22 张子阳 推荐:

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

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

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

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

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

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

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

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

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