我的第一本算法书

四年前，当我决定找工作后大概又过一年时间，经历好几场面试又经由身边大佬提醒，我终于意识到自己作为技术人员所欠缺的点之一：深度不够。 我提升深度的方法，大致分作两个阶段。 第一阶段是看教学视频，视频来源于两位老师，它们是李建忠老师的《C++设计模式》，以及侯捷老师的一系列C++教学视频。 看设计模式当时，我的感受又分作两点，一是前人的抽象总结能力真厉害，二是搭建我们项目的几位哥哥好厉害，他们在项目中用到许多设计模式，那种学习同时能于实际项目中立马验证的感觉真不错。 看完侯捷老师的视频，我写过一篇更新以整理自己的收获：除收获技术认知之外，听侯捷老师沉稳、温和的讲课让我静心；知道底层原理之后的“胸中自有沟壑”，依然是我喜欢的评语。 第二阶段是看书，我已经整理过许多篇文章来讲述自己如何养成阅读习惯以及读书如何对我产生影响：我读很多书，很多不同类型的书，这些书帮助我以不同视角去看世界、看自己，其中一个方向是技术。关于技术，近四年的读书，可以这样分类：从《Python源码剖析》，到HTTP: The Definitive Guide，到《操作系统导论》，再到《深入理解软件性能》，大概每年都有一本主要的每天都会阅读的技术书。 随着面试次数增多，我发现自己突破不了一面的很大一个原因是：算法题没做出来。刷题对我来说，是一件很难坚持事情，于是我便找寻折中方案：既然已经养成阅读习惯，不然在每天的某个固定时间段读一读专讲做题的书好啦？ 由此，我依次读完《程序员面试金典》《剑指Offer：专项练习版》《我的第一本算法书》，正阅读的是《算法（第4版）》。（对的，《算法》这本书，目前进展龟速……） 《我的第一本算法书》，今年3月便已经读完，这本书的作者是一位日本作家，有日本作家那种简练、实用风格，简练于是短小；本书，算是一本算法方向的入门书籍。作者在书中说：“数据存储于内存时，决定了数据顺序和位置关系的便是‘数据结构’，而算法是借助于数据结构来计算或者解决问题的步骤。” 我不确定自己迟迟不写本书读书笔记的原因是由于本书太短小，还是在于就算法和数据结构这一块的理解不够自信；总之，就这样一周周耽搁下来。转眼已到10月，今年已经读完但没写读书笔记的书还有很多，可不能再拖。 我强迫自己先靠记忆行事，列举出数据结构与算法都有哪些内容。 常用的数据结构有数组、字符串（也可以算作数组）、链表、队列（先进先出）、栈（后进先出）、哈希表、树（二叉树感觉出现的会更多些、B+树曾经有过一篇博客整理、堆也是一种树）、图。 排序是最基础内容，绝大部分基于数组，有时候会和链表联动，也会需要对链表进行排序。 （关于排序，我曾经有一个囧囧问答。面试官问我：“归并排序知道么？”我回答说：“我不太知道，但比较熟悉冒泡排序。”啊！当我会为面试做些准备时候，开始对这回答感到惭愧，特别是我说自己熟悉冒泡排序时，似乎还带着些骄傲情绪。） （啊哈哈，我现在写出来其实是有脸红的，记下之后又生出些坦然，坦然接受当年那个不想着跳槽的我；然后，读书笔记偏了题，我将本篇加到“第四份工作”系列。） 对排序过的数据进行二分查找，会将时间复杂度从遍历的O(n)缩小到O(log2n)。 如果某个题目某种场景中需要对字符串或是链表做些判定（比如字符串是否回文，链表是否有环），可以使用的算法之一叫做“双指针”，一快一慢或者一前一后。 哈希表，常用来以空间换时间，当数据存储于哈希表时，定位数据的时间复杂度，可以缩小到O(1)。 队列与栈的实现，可以是一道题目。但它们更多是给其它算法打辅助，比如二叉树的广度优先搜索，需要用到队列，而深度优先搜索，则使用栈。 书中内容虽然简洁，但除了以上我能看懂部分之外，还有安全算法以及许多需要很花时间、心力去学习的内容，比如回溯法、动态规划、聚类、A*等。 回溯法和动态规划，很常见，我在阅读当时有搞懂算法流程。但现在？老话常谈，我已然不能（阅读当时也不太能）使用自己语言将它们呈现出来。 《我的第一本算法书》是一本有许多图片的书，书中图片很好看，对算法的阐述很直观。然而，仅仅看书真的能够帮助自己提高做题成功率么？ 就我的经验来看，答案是可以的。 随着看的算法、解法多些，我开始对算法有一种“慢慢都能理解”的感受。对的，此处又关于读书，即便读过之后会忘记，但一点点积攒，借不同书一遍遍思考，慢慢将那些不熟悉记忆变做较熟悉的，较熟悉的变做熟悉的，慢慢汇总成一种对于数据结构和算法的一个笼统信心：算法题并不难，一点点回忆，是能想出解决方案来的，请不要害怕。 当然，临上阵时依然会紧张，那些不熟悉题目，在有限时间内依然会做不出来。这信心对我说：“别怕，你过去的积攒已经让成功做题的概率，更大了些。” 最后，要再谈一谈我对面试中需要做算法题态度的转变。最开始，我是全不知道面试要现场做题的，也就对面试不做准备，全靠工作中的不多积攒与面试当时的“聪明才智”。待发现面试时要做题，一开始的想法是抵触的：“这些工作中又不常用，真不知道考了做啥。”当自己看了些算法书，又生出许多崇拜：“还能这样做么？数据结构与算法确实该是计算机基础，多看些基础内容，对敲代码，对拓展思维，是真会有些帮助的。” 技术迭代很快，AI已经到来，对于“了解更多底层规则后对新事物的理解速度会变快”，我依然相信着。

上学期通过小破站先学了部分数据结构与算法，今天开设课程的第一节课，我坐在一个靠墙的位置边看这本书边在自己的书上做笔记，特别简单易懂。我对计算机其实是有些兴趣指引的，但大一一整年都在学各种数学，我也学得一塌糊涂哈哈。还有相对于学校开的C语言课程，我更想学习与人工智能相关性更大的Python语言……等等等等。意识到，跟着老师走，等着他/她来投喂，对我来说是一种惰性，吸收的知识不够，遗忘速度太快…所以采用主动学习的状态，加油啦

什么是能力？把晦涩难懂的专业术语变成简单通俗的语言传达给你。这本书就是如此。越来越喜欢阅读这类轻松的书，在学习中体会快乐，在快乐中收获知识！ 若上学时有幸遇见这本书，可能会对数据结构和各类算法理解得更加透彻吧！好在现在也不晚。 有趣，值得一读。

日本人写的知识工具书、科普书或技术教程都非常容易懂，真保姆式教学，把读者当作白纸一般初学者对待。另外，日本教材普遍喜欢利用图解大大降低理解难度。 但比起书我还是喜欢视频讲解，就去B站搜索了排序算法，竟然发现有人利用谷歌的notebookLM把整本书都做成了教学视频，视频合集叫“第一本算法书”。心中佩服，虽然我也用它整理知识和做ppt，但搞一整套教学视频还是很花功夫。

对于算法初学者是很好的读物，配合精彩的插图，简洁的描述，感觉全书脉络很清晰，希望顺着这个思路，可以多介绍些东西。 对于聚类算法，之前了解的比较少，前段时间算法同事分享聚类知识，到现在看到这里更清楚了些，很不错，了解算法第一步。

《我的第一本算法书》以大量动画式插图，将链表、数组、栈等 7 种数据结构及二分查找、快速排序等 26 个基础算法的原理与操作娓娓道来，大幅降低了抽象概念的理解门槛。排版清新、色彩柔和，对没有深厚数学背景的读者也十分友好，被多篇读者称为“人人都能看懂的算法入门书”。书中每章配合步骤图与实战示例，帮助读者在阅读过程中就能动手验证，对编程初学者和需要系统复习算法的职场人都颇具实用价值。若你渴望在轻松的视觉体验中迅速建立算法与数据结构的整体框架，这本书会是理想的起点。 下面是一些总结： 第1章　数据结构 • 本章指出数据结构决定数据在内存中的排列方式，并通过电话簿示例说明顺序与索引的权衡。 • 1-2 链表：数据分散、靠指针串联，插入删除 O(1)，但访问需从头开始，适合频繁修改的场景。 • 1-3 数组：支持随机访问，但插入删除需移动元素，时间复杂度均为 O(n)；适合读多写少。 • 1-4 栈：后进先出，典型应用是表达式匹配与深度优先搜索。 • 1-5 队列：先进先出，用于广度优先搜索等需要“先来先服务”的场合。 • 1-6 哈希表：利用哈希函数加速查询，冲突可用链地址法或开放地址法处理；在密码学中需注意哈希的不可逆性。 • 1-7 堆：树形结构，父节点不大于子节点，根节点最小，支持 O(1) 取最值与 O(log n) 调整，常用于优先队列和 Dijkstra 算法。 • 1-8 二叉查找树：左子树所有节点小于根，右子树大于根，查找、插入、删除平均 O(log n)，最坏情况取决于树高；可通过平衡机制保持效率。 第2章　排序 • 本章指出排序是将序列按升序排布的过程，并展示了冒泡、选择、插入、堆、归并、快速等常见算法。 • 2-2 冒泡排序：通过相邻交换把最小元素逐步浮到左侧，最坏与平均复杂度均为 O(n²)。 • 2-3 选择排序：每轮找剩余最小元素与左端交换，比较次数相同但交换次数少，复杂度仍为 O(n²)。 • 2-4 插入排序：维护已排好序的前缀，右侧元素逐个插入，最坏 O(n²)，但在近乎有序序列上表现佳。 • 2-5 堆排序：利用堆性质，整体复杂度 O(n log n)，比冒泡等更高效。 • 2-6 归并排序：分治思想，拆分到单元素后合并，总时间 O(n log n)。 • 2-7 快速排序：随机选基准值 partition 后递归，期望 O(n log n)，最坏 O(n²)，实践中最快。 第3章　数组的查找 • 3-1 线性查找：从数组首元素开始逐个比较，适用于无序数据，复杂度 O(n)。 • 3-2 二分查找：要求数组有序，每次将搜索范围减半，复杂度 O(log n)，在频繁查找、少量插入的场景优势明显。 第4章　图的搜索 • 本章首先定义图由顶点和边组成，并区分有向与无向图，为后续搜索算法奠定基础。 • 4-2 广度优先搜索：从起点层序扩展，最先发现的路径即最短，用于寻找无权图的最短路径。 • 4-3 深度优先搜索：沿一条路径尽可能深入，再回溯，实现上采用栈，适合探测连通分量或迷宫。 • 4-4 贝尔曼-福特算法：通过松弛边直到无更新，可处理负权重边，复杂度 O(nm)。 • 4-5 狄克斯特拉算法：结合优先队列选择当前最短距离顶点，复杂度 O(m + n log n)，不能处理负权重边。 • 4-6 A*算法：在狄克斯特拉基础上加入启发式评估，优先扩展最有希望的节点，可显著减少搜索节点数，常用于游戏路径寻找。 第5章　安全算法 • 本章概述互联网通信需解决的窃听、假冒、篡改、否认四大问题，并引入加密、MAC、数字签名、证书等技术。 • 5-2 加密基础：对称加密使用同一密钥加解密，示例凯撒密码、AES；难点在于密钥分发。 • 5-3 哈希函数：将任意数据映射为固定长度值，不可逆，用于密码存储等场景。 • 5-4 共享密钥加密：发送方与接收方使用同一密钥，加密速度快但密钥分发需额外保护。 • 5-5 公开密钥加密：成对密钥，公钥加密、私钥解密，解决密钥分发问题，但速度慢。 • 5-6 混合加密：结合对称与非对称优点，先用对称加密数据，再用非对称加密对称密钥，SSL/TLS 即采用此方案。 • 5-7 迪菲-赫尔曼密钥交换：双方在不安全信道中协商出共享密钥，安全性依赖离散对数难题。 • 5-8 消息认证码：利用共享密钥生成 MAC，可检测篡改但无法证明来源；用于保证数据完整性。 • 5-9 数字签名：用发送方私钥签名，公钥验证，可提供来源认证与不可否认性，但需证书绑定公钥。 • 5-10 数字证书：由认证中心签发，用于验证公钥所有权，构建 PKI 信任链。 第6章　聚类 • 本章指出聚类是按相似性把数据分成簇的过程，相似性的定义取决于数据类型和应用场景。 • 6-2 k-means 算法：需预先指定 k，随机选中心迭代分配数据与更新中心，直至收敛；层次聚类则无需预设簇数，通过不断合并最近簇完成。 第7章　其他算法 • 7-1 欧几里得算法：辗转相除求最大公约数，时间复杂度接近 O(log min(a,b))。 • 7-2 素性测试：试除法适合小数，费马测试与改进的米勒-拉宾用于大数；AKS 证明了多项式时间素性检测可行但实际常以费马测试为主。 • 7-3 网页排名：通过链接结构计算网页重要性，用随机跳转模型解决环状链接导致的无限循环问题。 • 7-4 汉诺塔：递归思想的经典示例，证明了任何 n 个圆盘均可在 2ⁿ⁻¹ 步内完成移动。

世界图书日时买了几本人工智能（AI）相关的书籍，刚看完《算法图解》与《我的第一本算法书》这两本，前一本是美国人写的，后一本是日本人写的。虽然都是写算法的书，也都是用图说明算法的书，但差异还是蛮大！ 算法是什么呢？——计算或解决问题的步骤。算法与程序有些相似，区别在于：程序是以计算机能够理解的编程语言编写而成，可在计算机上运行；算法是以人类能够理解的方式描述的，用于编写程序之前。不过，这个过程中，到哪里为止是算法、从哪里开始是程序，并没有明确的界限。 即使同一个算法，编程语言也许不同，写出来的程序也可能不同；即便使用相同的编程语言，写程序的人不同，编写出的程序也会不同。 算法的运行时间是从输入数据到输出数据结果这个过程所花费的时间。就算使用同样的算法，花费的时间也会根据所用计算机的不同而产生偏差。在这里，使用“步数”来描述运行时间，“1步”就是计算的基本单位。通过测试“计算从开始到结束总共执行了多少步”来求得算法的运行时间。  《我的第一本算法书》 先说明何为算法，与程序的区别； 然后分别介绍了7种数据结构； 最后是排序、查找、搜索、安全算法（哈希函数和7种加密），以及聚类（K-means算法）和其他算法（欧几里得算法、素性测试、网页排名、汉诺塔）的步骤和原理，每步都用一张图解说。的确是以人类能够理解的方式描述！ 而且逻辑非常清晰，比如，讲解完离散数学中的图、加权图、有向图后，随后介绍应用这些图的广度优先搜索、深度优先搜索，还有求最短路径的贝尔曼-福特算法（Bellman-Ford）、狄克斯特拉算法（Dijkstra）、A*（A-Star）算法。同样都是求最短路径，还会对比三种算法在不同情境下的优劣势。如果图中含有负数权重，不能使用狄克斯特拉算法：贝尔曼-福特算法可直接认定不存在的最短路径，但在狄克斯特拉算法中，即便不存在最短路径，也会算出一个错误的最短路径。距离估算值越接近当前顶点到终点的实际值，A-Star算法的搜索效率也越高；反之，若距离估算值与实际值相差较大，该算法的效率可能会比狄克斯特拉算法还要低；如果差距再大，甚至可能无法得到正确答案。 此书中没有介绍编程语言，更没有一步一步的编程代码。而《算法图解》第1章就说明书中示例都使用Python编写的一步一步代码，明确了编程语言是Python，而不是C语言、Ruby或其他。而实际上，算法可以用Python，也可以用C语言、Ruby或其他编程语言编写代码。所以，此书名好像改成“用Python编程语言编写算法与图解”更贴切[微笑] （连同另一本关于算法书籍，写了篇字数更多的读后感，于2019年7月5日发布在“N书斋”微信公众号，多谢指正[抱拳]）

1. 数据结构 主要讲了数组、链表、栈、队列、哈希表、堆、二叉查找树 在存储数据的过程中，如果发生冲突，可以利用链表在已有数据的后面插入新数据来解决冲突。这种方法被称为“链地址法”。除了链地址法以外，还有几种解决冲突的方法。其中，应用较为广泛的是“开放地址法”。这种方法是指当冲突发生时，立刻计算出一个候补地址（数组上的位置）并将数据存进去。如果仍然有冲突，便继续计算下一个候补地址，直到有空地址为止。可以通过多次使用哈希函数或“线性探测法”等方法计算候补地址。 堆是一种图的树形结构，被用于实现“优先队列”（priority queues），在堆中存储数据时必须遵守这样一条规则：子结点必定大于父结点。因此，最小值被存储在顶端的根结点中。往堆中添加数据时，为了遵守这条规则，一般会把新数据放在最下面一行靠左的位置。当最下面一行里没有多余空间时，就再往下另起一行，把数据加在这一行的最左端。 二叉查找树（又叫作二叉搜索树或二叉排序树）是一种数据结构，采用了图的树形结构。 二叉查找树有两个性质。第一个是每个结点的值均大于其左子树上任意一个结点的值。 第二个是每个结点的值均小于其右子树上任意一个结点的值。 首先，二叉查找树的最小结点要从顶端开始，往其左下的末端寻找。此处最小值为3。 比较的次数取决于树的高度。所以如果结点数为n，而且树的形状又较为均衡的话，比较大小和移动的次数最多就是log2n。因此，时间复杂度为O（logn）。但是，如果树的形状朝单侧纵向延伸，树就会变得很高，此时时间复杂度也就变成了O（n）。 有很多以二叉查找树为基础扩展的数据结构，比如“平衡二叉查找树”。这种数据结构可以修正形状不均衡的树，让其始终保持均衡形态，以提高查找效率。另外，虽然文中介绍的二叉查找树中一个结点最多有两个子结点，但我们可以把子结点数扩展为m（m为预先设定好的常数）。像这种子结点数可以自由设定，并且形状均衡的树便是B树。 2. 排序 主要讲了冒泡排序、选择排序、插入排序、堆排序、归并排序、快速排序。 在冒泡排序中，第1轮需要比较n-1次，第2轮需要比较n-2次……第n-1轮需要比较1次。因此，总的比较次数为（n-1）+（n-2）+…+1≈n2/2。这个比较次数恒定为该数值，和输入数据的排列顺序无关。不过，交换数字的次数和输入数据的排列顺序有关。假设出现某种极端情况，如输入数据正好以从小到大的顺序排列，那么便不需要任何交换操作；反过来，输入数据要是以从大到小的顺序排列，那么每次比较数字后便都要进行交换。因此，冒泡排序的时间复杂度为O（n2）。 选择排序使用了线性查找来寻找最小值，因此在第1轮中需要比较n-1个数字，第2轮需要比较n-2个数字……到第n-1轮的时候就只需比较1个数字了。因此，总的比较次数与冒泡排序的相同，都是（n-1）+（n-2）+…+1≈n2/2次。每轮中交换数字的次数最多为1次。如果输入数据就是按从小到大的顺序排列的，便不需要进行任何交换。选择排序的时间复杂度也和冒泡排序的一样，都为O（n2）。 插入排序是一种从序列左端开始依次对数据进行排序的算法。在排序过程中，左侧的数据陆续归位，而右侧留下的就是还未被排序的数据。插入排序的思路就是从右侧的未排序区域内取出一个数据，然后将它插入到已排序区域内合适的位置上。 在插入排序中，需要将取出的数据与其左边的数字进行比较。就跟前面讲的步骤一样，如果左边的数字更小，就不需要继续比较，本轮操作到此结束，自然也不需要交换数字的位置。然而，如果取出的数字比左边已归位的数字都要小，就必须不停地比较大小，交换数字，直到它到达整个序列的最左边为止。具体来说，就是第k轮需要比较k-1次。因此，在最糟糕的情况下，第2轮需要操作1次，第3轮操作2次……第n轮操作n-1次，所以时间复杂度和冒泡排序的一样，都为O（n2）。和前面讲的排序算法一样，输入数据按从大到小的顺序排列时就是最糟糕的情况。 堆排序一开始需要将n个数据存进堆里，所需时间为O（nlogn）。排序过程中，堆从空堆的状态开始，逐渐被数据填满。由于堆的高度小于log2n，所以插入1个数据所需要的时间为O（logn）。每轮取出最大的数据并重构堆所需要的时间为O（logn）。由于总共有n轮，所以重构后排序的时间也是O（nlogn）。因此，整体来看堆排序的时间复杂度为O（nlogn）。这样来看，堆排序的运行时间比之前讲到的冒泡排序、选择排序、插入排序的时间O（n2）都要短，但由于要使用堆这个相对复杂的数据结构，所以实现起来也较为困难。 归并排序算法会把序列分成长度相同的两个子序列，当无法继续往下分时（也就是每个子序列中只有一个数据时），就对子序列进行归并。归并指的是把两个排好序的子序列合并成一个有序序列。该操作会一直重复执行，直到所有子序列都归并为一个整体为止。 归并排序中，分割序列所花费的时间不算在运行时间内（可以当作序列本来就是分割好的）。在合并两个已排好序的子序列时，只需重复比较首位数据的大小，然后移动较小的数据，因此只需花费和两个子序列的长度相应的运行时间。也就是说，完成一行归并所需的运行时间取决于这一行的数据量。看一下上面的图便能得知，无论哪一行都是n个数据，所以每行的运行时间都为O（n）。而将长度为n的序列对半分割直到只有一个数据为止时，可以分成log2n行，因此，总共有log2n行。也就是说，总的运行时间为O（nlogn），这与前面讲到的堆排序相同。 快速排序算法首先会在序列中随机选择一个基准值（pivot），然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别，再将其排列成以下形式。[比基准值小的数] 基准值 [比基准值大的数]接着，对两个“[ ]”中的数据进行排序之后，整体的排序便完成了。对“[ ]”里面的数据进行排序时同样也会使用快速排序。 分割子序列时需要选择基准值，如果每次选择的基准值都能使得两个子序列的长度为原本的一半，那么快速排序的运行时间和归并排序的一样，都为O（nlogn）。和归并排序类似，将序列对半分割log2n次之后，子序列里便只剩下一个数据，这时子序列的排序也就完成了。 3. 图的搜索 主要讲了广度优先搜索、深度优先搜索、贝尔曼-福特算法、狄克斯特拉算法、A*算法。 图的搜索指的就是从图的某一顶点开始，通过边到达不同的顶点，最终找到目标顶点的过程。根据搜索的顺序不同，图的搜索算法可分为“广度优先搜索”和“深度优先搜索”这两种。 深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条候补路径。 深度优先搜索的特征为沿着一条路径不断往下，进行深度搜索。虽然广度优先搜索和深度优先搜索在搜索顺序上有很大的差异，但是在操作步骤上却只有一点不同，那就是选择哪一个候补顶点作为下一个顶点的基准不同。广度优先搜索选择的是最早成为候补的顶点，因为顶点离起点越近就越早成为候补，所以会从离起点近的地方开始按顺序搜索；而深度优先搜索选择的则是最新成为候补的顶点，所以会一路往下，沿着新发现的路径不断深入搜索。 将图的顶点数设为n、边数设为m，我们来思考一下贝尔曼-福特算法的时间复杂度是多少。该算法经过n轮更新操作后就会停止，而在每轮更新操作中都需要对各个边进行1次确认，因此1轮更新所花费的时间就是O（m），整体的时间复杂度就是O（nm）。 与前面提到的贝尔曼-福特算法类似，狄克斯特拉（Dijkstra）算法也是求解最短路径问题的算法，使用它可以求得从起点到终点的路径中权重总和最小的那条路径路径。 比起需要对所有的边都重复计算权重和更新权重的贝尔曼-福特算法，狄克斯特拉算法多了一步选择顶点的操作，这使得它在求最短路径上更为高效。将图的顶点数设为n、边数设为m，那么如果事先不进行任何处理，该算法的时间复杂度就是O（n2）。不过，如果对数据结构进行优化，那么时间复杂度就会变为O（m+nlogn）。 A*（A-Star）算法也是一种在图中求解最短路径问题的算法，由狄克斯特拉算法发展而来。狄克斯特拉算法会从离起点近的顶点开始，按顺序求出起点到各个顶点的最短路径。也就是说，一些离终点较远的顶点的最短路径也会被计算出来，但这部分其实是无用的。与之不同，A*就会预先估算一个值，并利用这个值来省去一些无用的计算。 4. 安全算法 哈希函数的算法中具有代表性的是MD5[插图]、SHA-1[插图]和SHA-2等。其中SHA-2是现在应用较为广泛的一个，而MD5和SHA-1存在安全隐患，不推荐使用。 加密数据的方法可以分为两种：加密和解密都使用相同密钥的“共享密钥加密”和分别使用不同密钥的“公开密钥加密”。 实现共享密钥加密的算法有凯撒密码、AES[插图]、DES[插图]、动态口令等，其中AES的应用最为广泛。 公开密钥加密是加密和解密使用不同密钥的一种加密方法。由于使用的密钥不同，所以这种算法也被称为“非对称加密”。加密用的密钥叫作“公开密钥”，解密用的叫作“私有密钥”。 X把密文发送给B，这个密文由B发出的公开密钥PB加密而成，所以B可以用自己的私有密钥SB来解密。从收到密文到解密密文都没发生任何问题，因此B也意识不到数据已经被窃听。这种通过中途替换公开密钥来窃听数据的攻击方法叫作“中间人攻击”（man-in-the-middle attack）。 公开密钥的可靠性会出现问题，就是因为A无法判断收到的公开密钥是否来自B。要想解决这个问题，就要用到之后会讲到的“数字证书”。公开密钥加密还有一个问题，那就是加密和解密都比较耗时，所以这种方法不适用于持续发送零碎数据的情况。要想解决这个问题，就要用到“混合加密”。 共享密钥加密存在无法安全传输密钥的密钥分配问题，公开密钥加密又存在加密解密速度较慢的问题。结合这两种方法以实现互补的一种加密方法就是混合加密。共享密钥加密存在无法安全传输密钥的密钥分配问题，公开密钥加密又存在加密解密速度较慢的问题。结合这两种方法以实现互补的一种加密方法就是混合加密。 消息认证码可以实现“认证”和“检测篡改”这两个功能。 数字签名不仅可以实现消息认证码的认证和检测篡改功能，还可以预防事后否认问题的发生。 通过数字证书，信息的接收者可以确认公开密钥的制作者。数字证书就是像这样通过认证中心来担保公开密钥的制作者。这一系列技术规范被统称为“公钥基础设施”（Public Key Infrastructure, PKI）。 5. 小结 第5章的安全算法很精彩！把各个算法用图描述的这么清楚还是比较难得的，我之前写了一篇相关算法的文章，画了几十张图前后花了一周的时间，费时费力，我是能体会出作者的用心的。

＃我的第一本算法书＃读后分享 首先这是一本深入浅出的书籍，相信即使不是软件出身的伙伴都能看的津津有味，这本书读它有什么作用呢？ 第一，你如果对了解如今各个app和网站都在做各类的推荐算法有兴趣，那么去了解算法背后的推荐机制根源，便是不错的入门方法，因为它可能来源于一些基础查询和排序算法，而这里面就涉及到从最基本的数据存储结构，也就是不同的数据结构，如链表、数组、堆栈、图、哈希表、队列、树，他们其实会根据不同场景得到不同应用，效率也不同。其中哈希表让我印象深刻。 哈希表存储的是键值对，大家可以理解为， 如果我们要存储多个类似于“小步-男”，这样的数据，在表中的顺序如果用1-n的方式去存储，那么数据越多，我们查找的时间越长，而这里哈希表的方式，就是把，“小步”进行哈希计算并按要存储数据的长度，取余数，将得到的值作为数组编号，这样后续做查找的时候，其实我们只需要查找“小步”的哈希值，便可快速得到数据，而不用线性查找 第二，网络世界由于开始蓬勃发展，网络安全已经是作为一个安全上网的支撑，因此，你可曾想过，如果你的所有通讯内容，可能被监听，或者你接收的内容被篡改，那么网络对于我们来说是怎样的存在？那这背后是有哪些加密方式在支撑呢，那么这本书会通过比较容易理解的图文告诉你关于对称加密，不对称加密，数字证书这些我们陌生的内容如果帮我们做好加密这一关。(以前学CCNA的时候咋没有发现这么通俗易懂的讲解) 第三，当你慢慢了解了算法在排序和查询方面那巧妙的计算原理，特别是图的概念后，你可能会将它的某些机理联想到生活中的方方面面，比如它采用的计算某个顶点到另一个顶点的最短路径权重方式，解决了复杂图节点的最小路径的计算。 最后，这本书某种意义上，就是完成对一些算法背景的了解，没有方法论可以获得，不过你阅读后，如果你是非开发人员，至少你会慢慢理解为啥有时候，我们在app中查询东西的时候，有些网站很快，有些很慢。很大可能就是，数据结构使用的差异和查询sql可能需要优化。

其实用配套的软件演示，比看这本书好，因为从动画演示中抽取部分图片有时候和文字匹配的不好，存在略微错位。 本书的排序，图搜索和安全三章可以看看，有个直观印象即可。因为没有涉及具体实现，一些描述可能存在困惑，例如那几种图搜索算法，其实需要队列，栈或者堆来存储候选节点，本书不会涉及这些，所以再走完一路选另一路时，新人可能会困惑。 还有一些描述不到位，有误的，看到的就在文中说了，这里不重复了。