《算法图解》摘抄 完整版

已经全部更新完了，这是一本非常友好的算法书籍。以下所有内容为本人的摘抄和阅读理解。（不包括第11章）

链表和数组

选择排序

递归

递归举例

栈

分而治之的思想

快速排序

如上图最糟情况，每次选择出基准点后要比较n次，一共需要选择n个基准点，因此时间复杂度就是O(n²)。在最佳情况中，每次选出基准点后要比较n次，一共选了logn个基准点，（原理和二分查找相同），因此时间复杂度为O(nlogn)
快速排序是最快的排序算法之一，也是分而治之思想的典范。

散列函数、散列表

图

广度优先搜索

᫲队列：先进先出； 栈：先进后出。
在广度优先搜索中，按照添加顺序进行查找，就是先添加一度关系，就查找一度关系；然后添加二度关系，以此类推。
这种按添加顺序进行查找可以使用队列进行实现，也就是说广度优先搜索使用队列实现。
可以把图使用散列表进行存储。例如：graph[‘bob’] = {‘ryan’, ‘alice’}说明bob的朋友有ryan和alice。
总结上边的一段话：图使用散列表存储，广度优先搜索算法使用队列实现。

代码运行以及队列情况如下图：

这个过程不断被执行，直到找到芒果商人或者队列为空。
但是有一个问题，如果多个人有共同的朋友，就会造成这个共同的朋友多次入队，也就是要查询多次这个共同的朋友。极端情况下，如果A和B互为朋友，则查询A不满足条件后，B入队；B不满足条件后，A入队…这是一个死循环。
因此，在检查完一个人之后，应该把他标注为已查询，从而避免重复查询同一个人。如下：

迪杰斯特拉算法

简单举例：


在无向图中，就是每一条边都是两个方向的，也就是说每一条边都是一个环，迪杰斯特拉算法无法处理有环图，因此迪杰斯特拉算法应用于有向无环图。

为了计算最终路径，需要在表中添加父节点这一列。

如果有负权边，就不能用迪杰斯特拉算法。

写代码的时候记住构建三个散列表就可以了，1是图（图中包含朋友节点和权重），2是开销表，3是父节点表。剩下的就是对以上三者的操作。

贪婪算法

问题：有一些备选州，有一些备选电台，每一个备选电台都可以覆盖某些州。找到尽量少的电台可以覆盖全部的州：

贪婪算法代码：

核心思想：每一次都找出最能覆盖余下州的电台。

NP完全问题

重点：记住集合覆盖和旅行商问题两个典型。

动态规划

核心思想：

总结来说其核心思想就是，在考察一个空格时，比较之前这个空格可以装载的最大价格，和，当前产品装进格子的价值与剩下的空间能容纳的最大价值之和，这两个结果哪个大，就放在当前格子中，就代表了目前情况下我可以偷的最贵重的商品。

行的顺序的变化不会对结果产生影响，就是说先算吉他和先算音响最后的结果是相同的。

动态规划不能解决只偷一部分商品的问题，例如只偷半袋米。但是贪婪算法可以解决这样的问题。（最后剩下的一点空间用价值最大的内容塞进去）

练习例子：

这个例子很简单，自己练习一下就行了。
下边是另一种情况。假如说每个子问题是相互依赖的，例如去不同的景点所消耗的时间不是独立的，而是相互依赖的，（例如去了a景点，距离b比较近，b景点的消耗时间就会减少）这种问题不同使用动态规划。

动态规划无法解决子问题之间相互依赖的问题。

K近邻

就是找到和“我”最近的K个点，其中哪种类型多，“我”就属于哪种类型。其中特征抽取是关键一步。因为要计算“我”与其他点的距离。如何衡量“我”与其他点在空间中的位置呢？
例如：两种水果，按两种特征来看，个头和颜色。换成数据就是（1，2）这样2维空间中的点。
如果是电影评分，一个人对五种类型电影的喜好程度就可以看做（1，3，4， 6， 3)这样5维空间中的点。
使用如下公式计算空间中两点的距离：

接下来是两个问题，以及答案：

如果使用KNN进行回归问题：

一个小问题：

接下来需要做的：
树：二叉查找树、B树、红黑树…
傅里叶变换