受小马的影响，也作为产品经理的视野拓展，最近对算法感兴趣了起来，因为暂时还没那么想写代码，就看了这本偏应用的算法书，感觉确实，虽然没记住多少，但是对算法思考的方式有了新的认识。

以下是小霍导出的读书笔记

我的第一本算法书

第2章 排序

冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字的位置”这一操作的算法。

像这样，在算法内部继续使用该算法的现象被称为“递归”。

第3章 数组的查找

它只能查找已经排好序的数据

二分查找必须建立在数据已经排好序的基础上才能使用，因此添加数据时必须加到合适的位置，这就需要额外耗费维护数组的时间。

第4章 图的搜索

由顶点和连接每对顶点的边所构成的图形就是图。

这个值叫作边的“权重”或者“权”，加了权的图被称为“加权图”。没有权的边只能表示两个顶点的连接状态，而有权的边就可以表示顶点之间的“连接程度”。
就是从图的某一顶点开始，通过边到达不同的顶点，最终找到目标顶点的过程。根据搜索的顺序不同，图的搜索算法可分为“广度优先搜索”和“深度优先搜索”这两种。
候补顶点是用“先入先出”（FIFO）的方式来管理的，因此可以使用“队列”这个数据结构。
广度优先搜索的特征为从起点开始，由近及远进行广泛的搜索。因此，目标顶点离起点越近，搜索结束得就越快
像示例那样的没有闭环的图叫作“树”。
深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条候补路径。01
狄克斯特拉（Dijkstra）算法也是求解最短路径问题的算法，使用它可以求得从起点到终点的路径中权重总和最小的那条路径路径。

第5章 安全算法

通过互联网交换数据时，数据要经过各种各样的网络和设备才能传到对方那里。数据在传输过程中有可能会经过某些恶意用户的设备，从而导致内容被盗取。

要想安全地使用互联网，安全技术是不可或缺的。本章将要学习的就是保障安全的各种算法和利用了这些算法的机制。

▶窃听

假冒

篡改：即便B确实收到了A发送的消息，但也有可能像右图这样，该消息的内容在途中就被X更改了。

▶事后否认

解决这些问题的安全技术
为了应对第一个问题“窃听”，我们会使用 “加密”技术。为了应对第二个问题“假冒”，我们会使用“消息认证码”或“数字签名”技术。
为了应对第三个问题“篡改”，我们同样会使用“消息认证码”或“数字签名”技术。其中“数字签名”技术还可以用于预防第四个问题“事后否认”
因此，我们需要给想要保密的数据加密。加密后的数据被称为“密文”。
B收到密文后，需要解除加密才能得到原本的数据。把密文恢复为原本数据的操作就叫作“解密”。
首先，计算机会用由0和1这两个数字表示的二进制来管理所有数据。如下图所示，数据虽然有文本、音频、图像等不同的形式，但是在计算机中都是用二进制来表示的。
加密就是数据经过某种运算后，变成计算机无法理解的数的过程

哈希函数：可以把给定的数据转换成固定长度的无规律数值。
哈希值虽然是数字，但多用十六进制来表示
第一个特征是输出的哈希值数据长度不变
第二个特征是如果输入的数据相同，那么输出的哈希值也必定相同。
第三个特征是即使输入的数据相似，但哪怕它们只有一比特的差别，那么输出的哈希值也会有很大的差异。输入相似的数据并不会导致输出的哈希值也相似。
第四个特征是即使输入的两个数据完全不同，输出的哈希值也有可能是相同的，虽然出现这种情况的概率比较低。这种情况叫作“哈希冲突”。
第五个特征是不可能从哈希值反向推算出原本的数据。输入和输出不可逆这一点和加密有很大不同。
最后一个特征是求哈希值的计算相对容易。
将用户输入的密码保存到服务器时也需要用到哈希函数
如果把密码直接保存到服务器，可能会被第三者窃听，因此需要算出密码的哈希值，并只存储哈希值。当用户输入密码时，先算出该输入密码的哈希值，再把它和服务器中的哈希值进行比对。这样一来，就算保存的哈希值暴露了，鉴于上文中提到的哈希函数的第五个特征（输入输出不可逆），第三者也无法得知原本的密码。就像这样，使用哈希函数可以更安全地实现基于密码的用户认证。

5-4 共享密钥加密

加密数据的方法可以分为两种：加密和解密都使用相同密钥的“共享密钥加密”和分别使用不同密钥的“公开密钥加密”。

共享密钥加密是加密和解密都使用相同密钥的一种加密方式。

由于使用的密钥相同，所以这种算法也被称为“对称加密”。

实现共享密钥加密的算法有凯撒密码、AES、DES、动态口令等，其中AES的应用最为广泛。

需要找到可以把密钥安全送出的方法，这就是“密钥分配问题”。

要想解决这个问题，可以使用“密钥交换协议”和“公开密钥加密”两种方法。

公开密钥加密：加密和解密使用不同密钥的一种加密方法。
实现公开密钥加密的算法有RAS算法、椭圆曲线加密算法等，其中使用最为广泛的是RSA算法。RSA算法由其开发者Rivest、Shamir、Adleman的首字母命名而来，三人在2002年获得了图灵奖。
如果使用共享密钥加密，密钥的需求数量会随着发送人数的增多而急剧增多。
公开密钥加密存在公开密钥可靠性的问题。
这种通过中途替换公开密钥来窃听数据的攻击方法叫作“中间人攻击”（man-in-the-middle attack）。
公开密钥的可靠性会出现问题，就是因为A无法判断收到的公开密钥是否来自B。
要想解决这个问题，就要用到“混合加密”。

5-6 混合加密

混合加密在安全性和处理速度上都有优势。

迪菲-赫尔曼密钥交换是一种可以在通信双方之间安全交换密钥的方法。
密钥的合成结果与合成顺序无关，只与用了哪些密钥有关。
这个密钥将作为“加密密钥”和“解密密钥”来使用。
因此，该方法又被叫作“迪菲-赫尔曼密钥协议”。
这个由密钥和密文生成的值就是消息认证码，以下简称为MAC（Message Authentication Code）。
加密仅仅是一个数值计算和处理的过程，所以即使密文被篡改了，也能够进行解密相关的计算。

5-9 数字签名

数字签名不仅可以实现消息认证码的认证和检测篡改功能，还可以预防事后否认问题的发生。

数字签名的生成使用的是公开密钥加密

其根本原因在于使用公开密钥加密无法确定公开密钥的制作者是谁。收到的公开密钥上也没有任何制作者的信息。

5-10 数字证书

通过数字证书，信息的接收者可以确认公开密钥的制作者。
此处的证书叫作“服务器证书”，同样由认证中心发行。个人的证书会与他的邮箱信息相对应，而服务器证书与域名信息相对应。

第6章 聚类

6-1 什么是聚类

聚类就是在输入为多个数据时，将“相似”的数据分为一组的操作。
如何定义“相似”▶定义数据间的

▶符合条件的算法

即使定义好了数据间的差距，聚类的方法也会有很多种。

下一节就将介绍其中最基本，也是最有代表性的聚类算法“k-means算法”。该算法可以把数据按要求分为k个簇。

6-2 k-means算法

k-means算法中，随着操作的不断重复，中心点的位置必定会在某处收敛，层次聚类算法不需要事先设定簇的数量。

第7章 其他算法

7-1 欧几里得算法

欧几里得算法（又称辗转相除法）用于计算两个数的最大公约数，被称为世界上最古老的算法。
首先用较小的数字去除较大的数字，求出余数。
接下来再用除数695和余数417进行mod运算。结果为278。
余数为0时，最后一次运算中的除数139就是1112和695的最大公约数。

7-2 素性测试

素性测试是判断一个自然数是否为素数的测试。

素数（prime number）就是只能被1和其自身整除，且大于1的自然数。
费马测试被称为概率性素性测试，它判断的是“某个数是素数的概率大不大”。
根据是否满足费马小定理来判断一个数是否为素数的方法就是“费马测试”。

如果p是素数，那么所有比p小的数n都满足np mod p=n这个条件。但反过来，即使所有n都满足条件，p也有可能不是素数。因为在极低概率下会出现所有n都满足条件的合数（非素数的自然数）。

7-3 网页排名

网页排名（PageRank，也叫作佩奇排名）是一种在搜索网页时对搜索结果进行排序的算法。此时可以使用“随机游走模型”（random walk model）来解决这个问题。

随机游走模型会直接将其作为网页的权重来使用。

7-4 汉诺塔

像这样，在算法描述中调用算法自身的方法就叫作“递归”。递归被运用到各种各样的算法中，这些算法统称为“递归算法”。