Grokking Algorithms
算法图解
目录
算法图解
这本书主要讲了什么?
总览
算法图解是一本兼顾数据结构和算法的入门书籍,以算法原理讲解为主,对于算法所涉及的相应数据结构,通常会在开篇前进行介绍,但并不深究其具体实现细节和底层操作逻辑,讲究够用原则。
作为入门书籍,该书并不过分追求大而全的写作思路,而是侧重以大量图示对经典算法的底层原理进行剖析,同时为力求读者产生场景共鸣,使得讲解通俗易懂,作者所选用算法解决的实际问题和案例说明基本都是源自于生活中常常会遇到的场景。
摘要
算法图解关注经典算法底层原理的图文解析,同时简要介绍所涉及到的数据结构。
详览
本书从使用频率较高的查找算法开始,介绍了依赖有序数列的二分查找算法(binary search algorithm),并与简单查找算法(遍历查找)的计算时间进行对比,引出算法复杂度的概念和大O表示法的基本原理,并简单举例一些常见的大O表达式的运行时间,如:
大O表示法 | 简称 | 举例 |
---|---|---|
$$O(logn)$$ | 对数时间 | 二分查找 |
$$O(n)$$ | 线性时间 | 简单查找 |
$$O(n*logn)$$ | - | 快速排序 |
$$O(n^2)$$ | 平方时间 | 选择排序 |
$$O(n!)$$ | 阶乘时间 | TSP问题 |
同时进一步讲解了选择排序算法的实现原理,并介绍了线性表(数组列表和链表)的实现原理以及内存工作原理,为更快速的对数列进行排序,进一步讲解了快速排序算法的实现原理,并介绍分治策略和递归的实现原理,以及栈对于递归策略的支撑,为更快速的对数列进行查找,进一步讲解了散列表的实现原理。
接下来,作者引入图的概念,讲解了用于求解最短路径问题的广度优先搜索算法和迪杰斯特拉算法,举例介绍了两种算法的不同之处和局限性,同时介绍了队列数据结构对于广度优先算法的支撑。
最后,作者讲解了贪婪算法求解NP难问题,并介绍了如何识别NP难问题以及常见的几种NP难问题,此外还介绍了动态规划算法的实现原理用于求解背包问题和最长公共子串问题。
最后的最后,作者介绍了最近比较流行的一些机器算法,如K最近邻算法,以及后续如何为深入学习算法做哪些准备。
警告
算法图解并未详细介绍树数据结构,虽然作者强调树可以认为是图的一个特殊实例,但是树作为高频使用的数据结构,读者有必要继续深入补充研究!