# Grokking Algorithms

<!--more-->

# 算法图解

## 这本书主要讲了什么？

### 总览

算法图解是一本兼顾**数据结构**和**算法**的**入门书籍**，以算法原理讲解为主，对于算法所涉及的相应数据结构，通常会在开篇前进行介绍，但并不深究其具体实现细节和底层操作逻辑，讲究**够用**原则。

作为入门书籍，该书并不过分追求大而全的写作思路，而是侧重以**大量图示**对经典算法的底层原理进行剖析，同时为力求读者产生场景共鸣，使得讲解通俗易懂，作者所选用算法解决的实际问题和案例说明基本都是源自于生活中常常会遇到的场景。

{{< admonition type=abstract title="摘要" open=true >}}
算法图解关注**经典算法**底层原理的图文解析，同时**简要介绍**所涉及到的数据结构。
{{< /admonition >}}

### 详览

![grokking_algorithm](https://raw.githubusercontent.com/WriteWhatLearned/imgs_repos/master/writing/202306172113146.png)

本书从使用频率较高的查找算法开始，介绍了依赖有序数列的**二分查找算法**（binary search algorithm），并与**简单查找算法**（遍历查找）的计算时间进行对比，引出算法复杂度的概念和**大O表示法**的基本原理，并简单举例一些常见的大O表达式的运行时间，如：

|   大O表示法   |   简称   |   举例   |
| :-----------: | :------: | :------: |
|  $$O(logn)$$  | 对数时间 | 二分查找 |
|   $$O(n)$$    | 线性时间 | 简单查找 |
| $$O(n*logn)$$ |    -     | 快速排序 |
|  $$O(n^2)$$   | 平方时间 | 选择排序 |
|   $$O(n!)$$   | 阶乘时间 | TSP问题  |

同时进一步讲解了**选择排序算法**的实现原理，并介绍了*线性表*（数组列表和链表）的实现原理以及内存工作原理，为更快速的对数列进行排序，进一步讲解了**快速排序算法**的实现原理，并介绍*分治策略*和*递归*的实现原理，以及*栈*对于递归策略的支撑，为更快速的对数列进行查找，进一步讲解了*散列表*的实现原理。

接下来，作者引入*图*的概念，讲解了用于求解最短路径问题的**广度优先搜索算法**和**迪杰斯特拉算法**，举例介绍了两种算法的不同之处和局限性，同时介绍了*队列*数据结构对于广度优先算法的支撑。

最后，作者讲解了贪婪算法求解**NP难问题**，并介绍了如何识别NP难问题以及常见的几种NP难问题，此外还介绍了**动态规划**算法的实现原理用于**求解背包问题**和**最长公共子串问题**。

最后的最后，作者介绍了最近比较流行的一些机器算法，如**K最近邻算法**，以及后续如何为深入学习算法做哪些准备。

{{< admonition type=warning title="警告" open=true >}}
算法图解并未详细介绍**树**数据结构，虽然作者强调树可以认为是图的一个特殊实例，但是树作为高频使用的数据结构，读者有必要继续深入补充研究！
{{< /admonition >}}

## 我从这本书里面学到了什么？

## 这本书给我的启发和思考有哪些？