算法图解-读书笔记
前言
首先要说明的是： 这本书的定义是一本算法入门书，更多的是以简单地描述和示例介绍常见的数据结构和算法以及其应用场景，所以如果你在算法上有了一定造诣或者想深入学习算法，这本书很可能不太适合你。
但如果你对算法感兴趣，但是不知从何学起或者感觉晦涩难懂，这本书绝对是一本很好的入门书，它以简单易懂的描述和示例，配以插画，向我们讲解了常见的算法及其应用场景。
本文是我基于自己的认知总结本书比较重点的部分，并不一定准确，更不一定适合所有人，所以如果你对本书的内容感兴趣，推荐阅读本书，本书总计180+页，而且配以大量示例和插画讲解，相信你很快就可以读完。
第一章：算法简介
算法是一组完成任务的指令。任何代码片段都可以视为算法。
二分查找
二分查找是一种用来在有序列表中快速查找指定元素的算法，每次判断待查找区间的中间元素和目标元素的关系，如果相同，则找到了目标元素，如果不同，则根据大小关系缩短了一半的查找区间。
相比于从头到尾扫描有序列表，一一对比的方式，二分查找无疑要快很多。
大O表示法
大O表示法是一种特殊的表示法，指出了算法的运行时间或者需要的内存空间，也就是时间复杂度和空间复杂度。
比如冒泡排序，
export default function bubbleSort(original:number[]) {
const len = original.length
for (let i = 0; i < len - 1; i++) {
for (let j = 1; j < len - i; j++) {
if (original[j - 1] > original[j]) {
[original[j - 1], original[j]] = [original[j], original[j - 1]]
}
}
}
}需要两层循环，每次循环的长度为 n(虽然并不完全等于n)，那它的时间复杂度就是 O(n²)。同时因为需要创建常数量的额外变量(len,i,j)，所以它的空间复杂度是 O(1)。
第二章：选择排序
内存的工作原理
当我们去逛商场或者超市又不想随身携带着背包或者手提袋时，就需要将它们存入寄存柜，寄存柜有很多柜子，每个柜子可以放一个东西，你有两个东西寄存，就需要两个柜子，也就是计算机内存的工作原理。计算机就像是很多柜子的集合，每个柜子都有地址。
数组和链表
有时我们需要在内存中存储一系列元素，应使用数组还是链表呢？
想要搞清楚这个问题，就需要知道数组和链表的区别。
数组是一组元素的集合，其中的元素都是相邻的，创建数组的时候需要指定其长度(这里不包括JavaScript中的数组)。可以理解为数组是一个大柜子，里边有固定数量的小柜子。
而链表中的元素则可以存储在任意位置，无需相邻，也不需要在创建的时候指定长度。
对应到电影院选座问题，
数组需要在初始就确定几个人看电影，并且必须是邻座。而一旦选定，此时如果再加一人，就需要重新选座，因为之前申请的位置坐不下现在的人数。而且如果没有当前数量的相邻座位，那么这场电影就没办法看了。
而链表则不要求指定数量和相邻性，所以如果是两个人，则只要还有大于等于两个空座，就可以申请座位，同样，如果此时再加一个人，只要还有大于等于一个空座，同样可以申请座位。\
数组因为可以通过索引获取元素，所以其读取元素的时间复杂度为O(1)，但是因为其连续性，在中间插入或者删除元素涉及到其他元素的移动，所以插入和删除的时间复杂度为O(n)。
链表因为只存储了链表的头节点，获取元素需要从头节点开始向后查找，所以读取元素的时间复杂度为O(1)，因为其删除和插入元素只需要改变前一个元素的next指针，所以其插入和删除的时间复杂度为O(1)。
选择排序
选择排序就是每次找出待排序区间的最值，放到已排序区间的末尾，比较简单，这里不做赘述了。
第三章：递归
个人理解，递归就是以相同的逻辑重复处理更深层的数据，直到满足退出条件或者处理完所有数据。
其中退出条件又称为基线条件，其他情况则属于递归条件，即需要继续递归处理剩余数据。
栈
这里主要讲的是调用栈，因为递归函数是不断调用自身，所以就导致调用栈也来越大，因为每次函数调用都会占用内存，当调用栈很高，就会导致内存占用很大的问题。解决这个问题通常有两种方法：
将递归改写为循环
使用尾递归
第四章：快速排序
快速排序使用的是分而治之的策略。
分而治之
简单理解，分治就是将大规模的问题，拆解为小规模的问题，直到规模小到很容易处理，然后对小规模问题进行处理后，再将处理结果合并，得到大规模问题的处理结果。
关于快排这里也不做赘述，感兴趣的可以看我之前的文章,需要注意的是，递归的方式更容易理解，但是会存在上述递归调用栈及多个子数组占用内存过高的问题。
第五章：散列表
散列表类似于JavaScript中的array、object和map，只不过作为上层语言，JavaScript帮我们做了很多工作，不需要我们自己实现散列函数，而散列函数，简单理解就是传入数据，会返回一个数字，而这个数字可以作为数组的索引下标，我们就可以根据得到的索引将数据存入索引位置。一个好的散列函数应该保证每次传入相同的数据，都返回相同的索引，并且计算的索引应该均匀分布。
常见的散列表的应用有电话簿，域名到IP的映射表，用户到收货地址的映射表等等。
冲突
散列表还有一个比较重要的问题是解决冲突，比如传入字符串"abc"，散列函数返回1，然后我们将"abc"存储在索引1的位置，而传入"def"，散列函数同样返回1，此时索引1的位置已经存储了"abc"，此时怎么办呢？
一种常见的解决方案是在每个索引的位置存储一个链表，这样就可以在一个索引位置，存储多个元素。
第六章：广度优先搜索
图
如果我们要从A去往B，而A去往B的路线可能很多条，这些路线就可以抽象成图，图中每个地点是图中的节点，地点与地点之间的连接线称为边。而如果我们要找出从A去往B的最近路径，需要两个步骤：
使用图来建立问题模型
使用广度优先搜索求解最短路径
广度优先搜索
所谓广度优先搜索，顾名思义，就是搜索过程中以广度优先，而不是深度，对于两点之间最短路径的问题，就是首先从出发点，走一步，看看是否有到达B点的路径，如果没有，就从第一步走到的所有点在走一步，看看有没有到达B点的路径，依此类推，直到到达B点。
实际算法中，广度优先搜索通常需要借助队列实现，即不停的把下一次能到达的点加入队列，并每次取出队首元素判断是否是B点，如果不是，再把它的下一个地点加入队列。
第七章：狄克斯特拉算法
在上一章我们可以使用广度优先搜索计算图的最短路径，但是如果图的每一条边都有相应的权重，也就是加权图，那么广度优先搜索求得的只是边数最少的路径，但是不一定是加权图中的最短路径，这个时候，想要求得最短路径，就需要狄克斯特拉算法。
狄克斯特拉算法的策略是：
每次都寻找下一个开销最小的节点
更新该节点的邻居节点的开销
重复这个过程，直到对图中每个节点都这样做
计算最终路径
但是要注意的是狄克斯特拉算法只适合权重为正的情况下使用，如果图中有负权边，要使用贝尔曼-福德算法。
第八章：贪婪算法
所谓贪婪算法，就是每一步都采用最优解，当所有的局部解都是最优解，最终所有局部最优解组合得到的全局解就是近似的全局最优解。
要注意的是，贪婪算法得到的并不一定是最优解，但是是近似最优解的结果。
可能你会有疑问，为什么不使用可以准确得到最优解的算法呢？这是因为有些问题很难求出准确的最优解，比如书中的城市路线问题。
如果只有2个城市，则会有2条路线
3个城市会有6条路线
4个城市会有24条路线
5个城市会有120条路线
6个城市会有720条路线
你会发现随着城市的增加，路线总数是城市数量的阶乘，当城市数量增加到一定程度，要枚举所有路线几乎是不可能的，这个时候就需要用贪婪算法求得一个近似的最优解。
第九章：动态规划
动态规划的主要思路是将一个大问题拆成相同的小问题，通过不断求解小问题，最后得出大问题的结果。
解题过程通常分为两步，状态定义和转移方程。
所谓状态定义，即抽象出一个状态模型，来表示某个状态下的结果值。
所谓转移方程，即推导出状态定义中的状态模型可以由什么计算得出。
以LeetCode 746. 使用最小花费爬楼梯为例： 因为最小花费只和台阶层数有关，所以可以定义 dp[i] 表示第i层台阶所需花费，这就是状态定义。
又因为第i层台阶可能从i-2上来，也可能从i-1上来，所以第i层台阶的最小花费等于前面两层台阶中花费更小的那个加上本层台阶的花费，即dp[i] = Math.min(dp[i-1],dp[i-2])+cost[i]，这就是转移方程。
完整解题代码如下：
var minCostClimbingStairs = function(cost) {
const dp = [cost[0],cost[1]]
for(let i = 2;i<cost.length;i++){
dp[i] = Math.min(dp[i-1],dp[i-2])+cost[i]
}
return Math.min(dp.at(-1),dp.at(-2))
}这里我讲解的方式和本书中画网格求解的方式并不一致，但是道理相同，一个是思考推导，一个是画网格推导。
第十章：K最近邻算法
K最近邻算法通常用来实现推荐系统，预测数值等。它的主要思想就是通过特征抽离，将节点绘制在坐标系中，当我们预测某个节点的数值或喜好时，通过对它相邻K个节点的数值和喜好的数据进行汇总求平均值，大概率就是它的数值和喜好。
比如常见的视频网站，社交网站，都会要求我们选择自己感兴趣的方面，或者在我们使用过程中记录我们的喜好，然后基于这些数据抽离我们的特征，然后根据相同特征的用户最近的观影记录或者话题记录，向我们推荐相同的电影和话题，也就是常见的猜你喜欢。还有机器学习的训练过程，也是提供大量数据给程序，让它进行特征抽离和记录，从而完善它的特征数据库，所以就有了机器越来越聪明的表现。
第十一章：接下来如何做
本章列举了本书没有单独拿出来讲但是依然很重要的数据结构和算法。
树
这里没有介绍树的基本概念，而是直接基于前面章节的二分查找引申出二叉查找树，这种树的性质是对于任意一个节点，它的左子树中的节点值都小于它，它的右子树的节点值都大于它。从而如果把整个树压平，就是一个升序的结果。然后还提到了B树，红黑树，堆和伸展树。
傅里叶变换
一个对傅里叶变换的比喻是：给她一杯冰沙，它能告诉你其中包含哪些成分。类似于给定一首歌曲，傅里叶变换能够将其中的各种频率分离出来。
常见的应用场景有音频、图片压缩。以音频为例，因为可以将歌曲分解为不同的频率，然后可以通过强调关系的部分，减弱或者隐藏不关心的部分，实现各种音效，也可以通过删除一些不重要的部分，实现压缩。
并行算法
因为笔记本和台式机都有多核处理器，那为了提高算法的速度，我们可以让它在多个内核中并行执行，这就是并行算法。
MapReduce
分布式算法是一种特殊的并行算法，并行算法通常是指在一台计算机上的多个内核中运行，而如果我们的算法复杂到需要数百个内核呢？这个时候就需要在多台计算机上运行，这就是分布式算法，MapReduce就是一种流行的分布式算法。
映射函数
映射函数接受一个数组，对其中的每个元素执行同样的操作。
归并函数
归并是指将多项合并于一项的操作，这可能不太好理解，但是你可以回想下归并排序和递归快排在回溯过程中合并结果数组的过程。
布隆过滤器 和 HyperLogLog
布隆过滤器 是一种概率型数据结构，它提供的答案有可能不对，但很可能是正确的。
比如Google负责搜集网页，但是它只需要搜集新出现的网页，因此需要判断该网页是否搜集过。固然我们可以使用一个散列表存储网页是否已经搜集过，查找和插入的时间复杂度都是O(1)，一切看起来很不错，但是因为网页会有数以万亿个，所以这个散列表会非常大，需要极大的存储空间，而这个时候，布隆过滤器就是一个不错的选择，它只需要占用很少的存储空间，提供的结果又很可能准确，对于网页是否搜集过的问题，可能出现误报的情况，即给出答案这个网页已搜集过，但是没有搜集，但是如果给出的答案是没有搜集，就一定没有搜集。\
HyperLogLog 是一种类似于布隆过滤器的算法，比如Google要计算用户执行的不同搜索的数量，要回答这个问题，就需要耗费大量的空间存储日志，HyperLogLog可以近似的计算集合中不同的元素数，与布隆过滤器一样，它不能给出准确的答案，但是近似准确答案，但是占用空间小很多。
以上两者，都适用于不要求答案绝对准确，但是数据量很大的场景。
哈希算法
这里介绍的就是哈希算法，常见的就是对文件进行哈希计算，判断两个文件是否相同，比如大文件上传中就可以通过计算文件的哈希值与已上传文件的散列表或者布隆过滤器比对，如果上传过，则直接上传成功，实现秒传。
还有一种应用场景就是密码的加密，通常用户输入的密码并不会进行明文传输，而是通过哈希算法进行加密，这样即使传输报文并黑客拦截，他也并不能知道用户的密码。书中还引申了局部敏感的散列函数，对称加密，非对称加密。
线性规划
线性规划用于在给定约束条件下最大限度的改善指定的指标。
比如你的公司生产两种产品，衬衫和手提袋。衬衫每件利润2元，需要消耗1米布料和5粒扣子；手提袋每个利润3元，需要消耗2米布料和2粒扣子。现在有11米布料和20粒扣子，为了最大限度提高利润，该生产多少衬衫好手提袋呢？
以上就是个人对 《算法图解》 这本书的读书总结，如果能给你带来一点帮助，那就再好不过了。
保持学习，不断进步！一起加油鸭！💪
作者：前端_奔跑的蜗牛
来源：https://juejin.cn/post/7097881646858240007
