0 序章

0-1 什么是算法

算法就是计算或者解决问题的步骤。

算法和程序的区别

算法和程序有些相似，区别在于程序是以计算机能够理解的编程语言编写而成的，可以在计算机上运行，而算法是以人类能够理解的方式描述的，用于编写程序之前。同一个算法，编程语言不同，写出来的程序也不同。

计算机是以这些基本命令的组合为基础运行的，面对复杂的操作，也是通过搭配组合这些基本命令来应对的。对于复杂操作，也就等同于构思如何搭配组合计算机可以执行的那些基本命令来实现复杂操作。

如何选择算法

一般来说我们最为重视的是算法的运行时间，即从输入数据到输出结果这个过程所花费的时间。

0-2 运行时间的计算方法

使用“步数”来描述运行时间，通过测试“计算从开始到结束总共执行了多少步”来求得算法的运行时间。

符号O表示“忽略重要项以外的内容”，读音同Order，含义为“算法的运行时间最长也就是 $ n^2 $ 的常数倍”

1 数据结构

1-1 什么是数据结构

数据存储于内存时，决定了数据顺序和位置关系的便是“数据结构” 。

例子

使用电话簿记录，如下

1、当没有顺序直接添加排列时，若需要查询“张伟”，则需要一个个找，这时查询成本较大

2、若按照姓名排序，若需要查询“张伟”，则很快可找到，但若需要插入“李华”时，需要将李华后面的记录下移

两种方法比较：

第一种方法插入效率高，查询效率低；第二种方法插入效率低，查询效率高。因此，对于经常查询的数据集，应采用第二种方法，对于经常插入的数据集，应采用第一种方法

1-2 链表

链表中数据呈线性排列，特点：插入效率高，查询效率低

概念图

存储结构

链表中，各节点是分散存储在内存中，无需连续存储

查询

若需访问Red，则需从Blue开始逐个访问，这便是顺序访问

插入

直接指针指向位置变化即可

删除

若要删除Yellow，则Green指向Red即可，虽然Yellow本身还存储在内存中，但是不管从哪里都无法访问这个数据，之后用新数据覆盖这个内存空间即可。

复杂度

查询： $ O\left( n \right) $

插入、删除： $ O\left( 1 \right) $

循环链表

循环链表也叫“环形链表” ，循环链表没有头和尾的概念，想要保存数量固定的最新数据时通常会使用这种链表。

双向链表

这种链表，不仅可以从前往后，还可以从后往前遍历数据。

缺点：

指针数的增加会导致存储空间需求增加
添加和删除数据时需要改变更多指针的指向

1-3 数组

概念图

存储结构

在内存空间中连续存储

查询

由于连续存储，因此每个数据的内存地址可通过下标计算得出，直接访问数据（C语言中指针概念，Java中直接数组访问a[2]）

插入

若要将Green插入到a[1]的位置，则需要：

开辟一个新的内存空间
依次将数据向后挪，腾出a[1]的位置
将Green存入到a[1]中

删除

若要删除a[1]中的元素，和插入相同，步骤为：

删除目标数据
依次将a[1]之后的内容向前挪动

复杂度

查询： $ O\left( 1 \right) $

插入、删除： $ O\left( n \right) $

数组和链表的比较

1-4 栈

特点：栈这种最后添加的数据最先被取出，即“后进先出”的结构，称为 Last In First Out，简称 LIFO

栈的数据也是线性排列，在栈中，添加和删除数据的操作只能在一端进行，访问数据也只能访问到顶端的数据。想要访问中间的数据时，就必须通过出栈操作将目标数据移到栈顶才可以。

1-5 队列

队列中的数据也呈线性排列，队列这种最先进去的数据最先被取来，即“先进先出”的结构，我们称为 First In
First Out，简称 FIFO。

队列中添加和删除在两端进行，因此队列也不能直接访问位于中间的数据，必须通过出队操作将目标数据变成首位后才能访问。

1-6 哈希表

通过一个例子进行说明，哈希表使用的是数组+链表来进行存储

哈希表中存储的是由键（key）和值（value）组成的数据。

首先开辟5个连续的内存空间

通过哈希函数Hash计算Joe的值为4928

将Joe的哈希值对5取模

之后的元素依次执行以上操作

此时，Nell和Sue发生冲突，这时改变新的存储结构，使用链表存储

全部存储完成后为

若要查询Ally的数据，则先计算Ally的哈希值

查询到的内容为Joe，然后对Joe所在的链表进行线性查找

问题：如果数组的空间太小，使用哈希表的时候就容易发生冲突，便需要添加链表，线性查找的使用频率将会更高；如果数组的空间太大，将会造成内存的浪费。因此设定合适的数组长度非常重要。

应对数组存储时的冲突，以上介绍的为链地址法，除了链地址法外，还有开放地址法，这种方法是指当存储发生冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。可以通过多次使用哈希函数或“线性探测法”（线性探测发就是依次寻找下一个地址，看是否为空可插入）等方法计算候补地址。

1-7 堆

堆是一种图的树形结构，被用于实现“优先队列”，优先队列是一种数据结构，可以自由添加数据，但取出数据时要从最小值开始按顺序取出。在堆的树形结构中，各个顶点被称为“结点”，数据就存储在这些结点中。

节点内的数字为存储的数据，堆中的每个结点最多有两个子结点。树的形状取决于数据的个数，结点的排列顺序为从上到下，同一行里则为从左到右。

规则：子结点总是大于等于或小于等于父结点。

最小值被存储在根节点，往堆中添加数据时，一般会把新数据放在最下面一行靠左的位置。当最下面一行里没有多余空间时，就再往下另起一行，把数据加在这一行的最左端。因此，每行必须添加满了后才可再次开启下一行。

添加

向堆中添加5

删除

从堆中取出数据时，取出的是最上面的数据（最小的数据）。

接下来对堆的结构进行调整

将最后一个元素移动到最顶端

若子结点的数字小于父结点，则将父结点与其左右两个子结点中较小的一个进行交换。这里由于6大于子节点3（左）和5（右），将左边的子结点与父结点进行交换。

再进一步进行交换调整，结束

说明

堆中最顶端的数据始终最小，所以无论数据量有多少，取出最小值的时间复杂度都为 $ O\left( 1 \right) $

取数据时，需要将最后的数据移到最顶端，然后一边比较它与子结点数据的大小，一边往下移动，所以取出数据需要的运行时间和树的高度成正比。若数据量为 $ n $ ，则数的高度为 $ {\log _2}n $ ，因此重构数的时间复杂度为 $ O\left( {{{\log }_2}n} \right) $

添加数据也相同，在堆的最后添加数据后，需要比较与父节点的大小，并向上移动，因此也和数的高度成正比，时间复杂度也为 $ O\left( {{{\log }_2}n} \right) $

1-8 二叉查找树

结点中的数字为存储的数据

二叉查找树有两个特性：

每个结点的值均大于其左子树上任意一个结点的值，例如9大于3和8
每个结点的值均小于其右子树上任意一个结点的值，例如15小于23,17,28

在这个特性下，查找最小值要从顶端开始，往其左下的末端寻找。查找最大值要从顶端开始，往其右下的末端寻找

添加

首先从二叉查找树的顶端结点开始寻找位置，若该数字小于顶端结点，则左移，若大于顶端结点，则右移

同理，若添加数字4，则为

删除

1、删除没有子结点的结点，直接删除即可

2、删除有一个子结点的结点，将子结点直接替换到被删除节点的位置上即可

3、删除有两个子结点的结点，在被删除结点的左子树中寻找最大结点，然后将最大结点移到被删除结点的位置上

查询

查找节点12

说明

二分查找树是二分查找法树形结构的体现，在查找数据或寻找适合添加数据的位置时，只要将其和现有的数据比较大小，就可以根据比较结果得知该往哪边移动了。

比较的次数取决于树的高度。结点数为 $ n $ ，若数较为均衡，比较大小和移动的次数最多为 $ {{{\log }_2}n} $ ，时间复杂度为 $ O\left( {{{\log }_2}n} \right) $ ；若数的形状朝单侧纵向延伸，树就会变得很高，此时时间复杂度也就变成了 $ O\left( n \right) $

补充

以二叉查找树为基础，对其进行拓展，修正形状不均衡的树，让其始终保持均衡形态，以提高查找效率，称为“平衡二叉查找树” 。二叉查找树中一个结点最多有两个子结点，可以把子结点数扩展为 $ m $ ，这种子结点数可以自由设定，并且形状均衡的树便是 B 树。

2 排序

2-1 什么是排序

排序就是将输入的数字按照从小到大或从大到小的顺序进行排列。

接下来说明几种排序算法，假设输入的数字个数为 n，且输入的一组数据中无重复数字。实际上，即使有相同的数字，算法依然可以正常运行。

2-2 冒泡排序

冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字的位置”这一操作的算法。在这个过程中，数字会像泡泡一样，慢慢从右往左“浮”到序列的顶端，所以这个算法才被称为“冒泡排序” 。

交换7和6

4和6无需交换。

依次进行，直到到达最左边，通过这一系列操作，序列中最小的数字就会移动到最左边。

说明

时间复杂度： $\left( {n - 1} \right) + \left( {n - 2} \right) + ... + 1 \approx \frac{{{n^2}}}{2} $ ，因此为 $ O\left( {{n^2}} \right) $

2-3 选择排序

选择排序就是重复“从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换”。在序列中寻找最小值时使用的是线性查找。

重复操作直到所有排序完成

说明

时间复杂度：和冒泡排序一样， $\left( {n - 1} \right) + \left( {n - 2} \right) + ... + 1 \approx \frac{{{n^2}}}{2} $ ，因此为 $ O\left( {{n^2}} \right) $

2-4 插入排序

插入排序是一种从序列左端开始依次对数据进行排序的算法。在排序过程中，左侧的数据陆续归位，而右侧留下的就是还未被排序的数据。

插入排序的思路就是从右侧的未排序区域内取出一个数据，然后将它插入到已排序区域内合适的位置上。

对以上数据进行排序

第一轮左边只有一个数字5，不需要排序

第二轮比较3和5的大小，由于3<5，因此交换

接下来查看4，先将4和5进行比较，交换；再将4和3进行比较，不交换

依次执行以上操作，直到所有数字完成排序

说明

插入排序的时间复杂度为 $ O\left( {{n^2}} \right) $

2-5 堆排序

堆排序的特点是利用了数据结构中的堆。

首先，在堆中存储所有的数据，并按降序（子结点大于父结点）来构建堆

为了排序，需要再从堆中把数据一个个取出来。从降序排列的堆中取出数据时会从最大的数据开始取，所以将取出的数据反序输出，排序就完成了。

对堆进行重构

再次取出根节点

依次执行以上步骤，直到所有数据取出，排序完成

说明

将数据存入到堆中，所需的时间复杂度为 $ O\left( {n\log n} \right) $ ，每次取数据后，堆需要进行重构，总共取n轮，因此重构的时间复杂度为 $ O\left( {n\log n} \right) $ ，总体来看，堆排序的时间复杂度为 $ O\left( {n\log n} \right) $

因此可发现，堆排序和冒泡排序、选择排序、插入排序相比，所用时间复杂度最低，但由于使用堆这个相对复杂的数据结构，实现也较为麻烦

补充

一般来说，需要排序的数据都存储在数组中。而以上使用的堆的这种数据结构，事实上，相当于将堆嵌入到包含了序列的数组中，然后在数组中通过交换数据来进行排序。可以说是强行在数组中使用了堆结构。

2-6 归并排序

2-6-1自顶向下的归并排序

归并排序算法会把序列分成长度相同的两个子序列，当无法继续往下分时（也就是每个子序列中只有一个数据时），就对子序列进行归并。归并指的是把两个排好序的子序列合并成一个有序序列。该操作会一直重复执行，直到所有子序列都归并为一个整体为止。

首先，对半分割

分割完毕，接下来对分割后的元素进行合并

接下来说明如何合并[4,6]和[3,7]。首先，先比较两个子序列的首位数字3和4，然后将较小的（3）移动，再移动较大的（4）。接下来再比较两子序列剩余的数字，也按照相同规则。

对右边的5，1，2也进行归并

最后对两个子序列进行归并，排序完成

2-6-2 自底向上的归并排序

自底向上的归并排序算法的思想就是数组中先一个一个归并成两两有序的序列，两两有序的序列归并成四个四个有序的序列，然后四个四个有序的序列归并八个八个有序的序列，以此类推，直到，归并的长度大于整个数组的长度，此时整个数组有序。

需要注意的是数组按照归并长度划分，最后一个子数组可能不满足长度要求，这个情况需要特殊处理。

说明

归并排序中，分割序列所花费的时间不算在运行时间内（可以当作序列本来就是分割好的）。在合并两个已排好序的子序列时，只需重复比较首位数据的大小，然后移动较小的数据，因此只需花费和两个子序列的长度相应的运行时间。也就是说，完成一行归并所需的运行时间取决于这一行的数据量。

自顶向下的归并排序算法一般用递归来实现，而自底向上可以用循环来实现。

无论哪一行都是n个数据，所以每行的运行时间都为 $ O\left( n \right)$ ，而共 $ {\log _2}n $ 行，因此时间复杂度为 $ O\left( {n\log n} \right) $ ，与堆排序相同

2-7 快速排序

快速排序算法首先会在序列中随机选择一个基准值（pivot），然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别，再将其排列成以下形式：

接下来看排序步骤：

1、对以下数据进行排序

2、随机选取一个基准值，选4

3、将剩余数字依次和基准值比较，小于基准值的左移，大于基准值的右移

4、结果为

5、接下来就是的对左右两边进行排序

6、两边操作相同，以右边为例，仍然采用以上排序方法，随机选择基准值，为6

7、排序结果为

8、再次对8,9,7进行快速排序，随机选取基准值，为8

9、排序结果为

10、这时右边完成了排序操作

11、同理，对左边进行排序，然后整个序列排序完成

说明

快速排序和归并排序相似，将序列对半分割 $ {\log _2}n $ 次后，子序列中只剩一个数字，带入到归并排序中，共 $ {\log _2}n $ 行，每行中需要n次排序，因此，整体的时间复杂度为 $ O\left( {n\log n} \right) $

补充

快速排序是一种“分治法” 。它将原本的问题分成两个子问题（比基准值小的数和比基准值大的数），然后再分别解决这两个问题。对子序列排序后，再把他们合并成一个序列，那么对原始序列的排序也就完成了。

在解决子问题的时候会再次使用快速排序，甚至在这个快速排序里仍然要使用快速排序。只有在子问题里只剩一个数字的时候，排序才算完成。

可发现，可用递归方法，在算法内部继续使用该算法的现象被称为“递归” 。

2-8 希尔排序

摘自博客图解排序算法(二)之希尔排序

希尔排序是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。

一般来说，希尔排序的时间复杂度低于 $ O\left( {{n^2}} \right) $

2-9 基数排序

参考博客基数排序详解以及java实现

基数排序又称为桶排序，基数排序是一种分配式排序，即通过将所有数字分配到应在的位置最后再覆盖到原数组完成排序的过程。基数排序牺牲了内存空间来换取时间复杂度。

在排序过程中，首先通过个位，将原数组放到“桶”中，再将其取出，得到个位数下有序的数组；再将其放到十位数的“桶”中，再将其取出，得到十位下有序的数组，如此循环....

可发现，基数排序思想是首先先通过对个位排序，再通过对十位排序....最终得到有序数组

若时间复杂度为 $ O\left( {{n}} \right) $

例如，数组为：73, 22, 93, 43, 55, 14, 28, 65, 39, 81

排序过程如下：

1、按个位排序

1	2	3	4	5	8	9
81	22	73	14	55	28	39
		93		65
		43

按个位排序后的结果为：81,22,73,93,43,14,55,65,28,39

2、按十位排序

1	2	3	4	5	6	7	8	9
14	22	39	43	55	65	73	81	93
	28

按十位排序后的结果为：14,22,28,39,43,55,65,73,81,93。排序完成

基数排序的两种方式：

高位优先，又称为最有效键(MSD),它的比较方向是由右至左；
低位优先，又称为最无效键(LSD),它的比较方向是由左至右；

3 数组的查找

3-1 线性查找

线性查找是一种在数组中查找数据的算法，和二分查找不同，即便数据没有按顺序存储，也可以应用线性查找。线性查找的操作很简单，只要在数组中从头开始依次往下查找即可。

线性查找的过程就是从数组第一个元素开始逐一查找。

说明

线性查找需要从头开始不断地按顺序检查数据，因此在数据量大且目标数据靠后，或者目标数据不存在时，比较的次数就会更多。

时间复杂度为 $ O\left( {{n}} \right) $

3-2 二分查找

二分查找只能在有序数组中查找指定数据。二分查找通过比较数组中间的数据与目标数据的大小，可以得知目标数据是在数组的左边还是右边。因此，比较一次就可以把查找范围缩小一半。重复执行该操作就可以找到目标数据，或得出目标数据不存在的结论。

1、查找6

2、找到中间数字5，和5比较大小

3、发现待查找的数字在5的右边

4、查找右边序列中的中间数字，进行比较

5、发现在中间数字的左边

说明

二分查找利用已排好序的数组，每一次查找都可以将查找范围减半。查找范围内只剩一个数据时查找结束。由于每次将数组长度减半，因此总共进行 $ log_2n $ 次查找，时间复杂度为 $ O\left( {{{\log }_2}n} \right) $

补充

与线性查找相比，二分查找的时间复杂度得到了指数性的提高。但是，二分查找必须建立在数据已经排好序的基础上才能使用，因此添加数据时必须加到合适的位置，这便造成了额外的时间损耗。而线性查找数组可以是无序的，因此在插入数据时，只需插入到数组末尾即可，无任何时间损耗。

综上，具体使用哪种查找方法，可以根据查找和添加两个操作哪个更为频繁来决定。

4 图的搜索

4-1 什么是图

计算机科学和离散数学中所说的图如下，图由定点和边构成。

图的例子

1、关系图

2、铁路图

3、计算机网络图

加权图

没有权的边只能表示两个顶点的连接状态，而有权的边就可以表示顶点之间的“连接程度” 。根据图的内容不同， “程度”表示的意思也不同。例如在计算机网络中，可用加权来表示不同节点间的通信时间。

有向图

与此相对，没有箭头的图便是“无向图” 。同理，有向图可也加上权重

图的优势

设计一种算法来寻找两个节点的权重和最小的最优路径。

本章知识点

1、图的搜索算法

图的搜索指的就是从图的某一顶点开始，通过边到达不同的顶点，最终找到目标顶点的过程。根据搜索的顺序不同，图的搜索算法可分为“广度优先搜索”和“深度优先搜索”这两种。

2、最短路径问题算法

最短路径问题和前文提到的一样，就是要在两顶点的路径中，找到一条所经过的边的权重总和最小的路径。

4-2 广度优先搜索

广度优先搜索是一种对图进行搜索的算法。从某个顶点（即起点）出发，不知道图的整体结构，从起点开始顺着边搜索，直到到达指定顶点（即终点）。在此过程中每走到一个顶点，就会判断一次它是否为终点。广度优先搜索会优先从离起点近的顶点开始搜索。

A为起点，G为终点，下图搜索的顺序为A,B,C,D,E,F,G,I,J,K,G

说明

广度优先搜索的特征为从起点开始，由近及远进行广泛的搜索。因此，目标顶点离起点越近，搜索结束得就越快。

补充

闭环

4-3 深度优先搜索

深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条候补路径。

A为起点，G为终点，以下搜索顺序是A,B,E,K,F,C,H,G

说明

深度优先搜索的特征为沿着一条路径不断往下，进行深度搜索。虽然广度优先搜索和深度优先搜索在搜索顺序上有很大的差异，但是在操作步骤上却只有一点不同，那就是选择哪一个候补顶点作为下一个顶点的基准不同。

广度优先搜索选择的是最早成为候补的顶点，因为顶点离起点越近就越早成为候补，所以会从离起点近的地方开始按顺序搜索；而深度优先搜索选择的则是最新成为候补的顶点，所以会一路往下，沿着新发现的路径不断深入搜索

4-4 贝尔曼 - 福特算法

贝尔曼 - 福特（Bellman-Ford）算法是一种在图中求解最短路径问题的算法。最短路径问题就是在加权图指定了起点和终点的前提下，寻找从起点到终点的路径中权重总和最小的那条路径。

1、A为起点，G为终点

2、首先设置各个顶点的初始权重：起点为0，其他顶点为无穷大（∞）

3、接下来更新每个顶点的权重，例如，B的权重9=0+9，表示从A到B的权重，若该权重值小于顶点原本权重值，则更新，在B中，由于9<∞，因此更新

4、同理，更新C的权重值

5、如此循环更新下去，直到所有顶点权重被更新，因此就找到了从起点到其余各个顶点的最短路径

6、从A到G的最短路径便被找到，权重为14

说明

图的顶点数为n，边数为m，需要n轮操作，每轮需要对所有边确认，因此一轮时间复杂度为 $ O(m) $ ，整体的时间复杂度为 $ O(nm) $

补充

计算最短路径时，边的权重代表的通常都是时间、距离或者路费等，因此基本都是非负数。不过，即便权重为负，贝尔曼 - 福特算法也可以正常运行。

但是，如果在一个闭环中边的权重总和是负数，那么只要不断遍历这个闭环，路径的权重就能不断减小，也就是说根本不存在最短路径。遇到这种对顶点进行 n 次更新操作后仍能继续更新的情况，就可以直接认定它“不存在最短路径” 。

4-5 狄克斯特拉算法

狄克斯特拉（Dijkstra）算法也是求解最短路径问题的算法，使用它可以求得从起点到终点的路径中权重总和最小的那条路径路径。

1、A为起点，G为终点，首先，除顶点外的其余所有顶点权重设为∞

2、寻找候补节点，然后对顶点值进行更新

3、对顶点进行移动

4、采用相同方法对B的候补顶点进行更新

5、移动到顶点D，这时由于权重大于原本权重，因此不需要更新

6、再从候补顶点C采用相同操作更新C的候补节点

7、接下来分别移动到E，F进行更新，更新顶点G的权重

8、最短路径为

说明

贝尔曼 - 福特算法需要对所有的边都重复计算权重和更新权重，而狄克斯特拉算法多了一步选择顶点的操作，这使得它在求最短路径上更为高效。

若图的顶点数设为 n、边数设为 m，不进行任何事先处理，时间复杂度为 $ O(n^2) $ ，可通过对数据结构进行优化将时间复杂度变为 $ O(m+n {log} n) $

补充

狄克斯特拉算法和贝尔曼 - 福特算法均可用于求最短路径问题

但二者的区别在于当路径权重为负数时狄克斯特拉算法可能会无法得出正确答案。如图，显然A-C-B-G为最短路径，然而若使用狄克斯特拉算法，则会选择A-B-G，这是因为选择候补节点时由于B(2)<C(4)，因此选择了B，导致结果错误。

因此，不存在负数权重时，更适合使用效率较高的狄克斯特拉算法，而存在负数权重时，即便较为耗时，也应该使用可以得到正确答案的贝尔曼 - 福特算法。

4-6 A* 算法

A*（A-Star）算法也是一种在图中求解最短路径问题的算法，由狄克斯特拉算法发展而来。狄克斯特拉算法按顺序求出起点到各个顶点的最短路径。也就是说，一些离终点较远的顶点的最短路径也会被计算出来，但这部分其实是无用的。与之不同，A * 会预先估算一个值，并利用这个值来省去一些无用的计算。

通过一个例子比较狄克斯特拉算法和A* 算法。

1、求S到G的最短路径，各顶点间的权重为1

2、若使用狄克斯特拉算法，蓝色表示都被搜索过，红色为最短路径，可发现，狄克斯特拉算法只根据起点到候补顶点的距离来决定下一个顶点。因此，它无法发现蓝色箭头所指的这两条路径其实离终点越来越远，同样会继续搜索。

3、A*算法不仅会考虑从起点到候补顶点的距离，还会考虑从当前所在顶点到终点的估算距离。估算距离可自由设定，这里采用S到G距离的四舍五入值。

所在顶点到起点的实际距离，再加上该顶点到终点的距离估算值，就是从起点到终点的估算距离。 “从起点到该顶点的距离” （方块左下），“距离估算值” （方块右下）

过程同样采用狄克斯特拉算法，结果如下

说明

若可得到顶点到终点的大致距离（这个距离不需是准确的值）我们就能使用 A* 算法。这样的算法也被称为启发式算法

距离估算值越接近当前顶点到终点的实际值，A* 算法的搜索效率也就越高；反过来，如果距离估算值与实际值相差较大，那么该算法的效率可能会比狄克斯特拉算法的还要低。如果差距再大一些，甚至可能无法得到正确答案。

不过，当距离估算值小于实际距离时，是一定可以得到正确答案的。

5 安全算法

5-1 安全和算法

传输数据时的四个问题

1、窃听

2、假冒

3、篡改

4、事后否认

B 从 A 那里收到了消息，但作为消息发送者的 A 可能对 B 抱有恶意，并在事后声称“这不是我发送的消息”。这种情况会导致互联网上的商业交易或合同签署无法成立。

解决这些问题的安全技术

窃听：使用加密技术
假冒：使用“消息认证码”或“数字签名” 技术。
篡改：同样会使用“消息认证码”或“数字签名”技术。
事后否认：“数字签名”技术

本章知识点

“数字签名”技术存在“无法确认公开密钥的制作者”这一问题。要想解决这个问题，可以使用“数字证书”技术。

5-2 加密的基础知识

讲解加密技术的必要性和基本原理。

1、若不进行加密，直接通过网络设备从A传给B，则可能会被第三者窃听

2、经过加密后，便可防止窃听，A端称为加密，B端称为解密

说明

加密的具体操作

首先，计算机会用由 0 和 1 这两个数字表示的二进制来管理所有数据

对计算机来说，数据就是一串有意义的数字罗列。密文也是数字罗列，只不过它是计算机无法理解的无规律的数字罗列。因此，加密就是数据经过某种运算后，变成计算机无法理解的数的过程

在加密运算上会用到“密钥” 。所以加密就是用密钥对数据进行数值运算，把数据变成第三者无法理解的形式的过程

反过来，解密就是像下图这样，通过密钥进行数值计算，把密文恢复成原本数据的过程。

5-3 哈希函数

哈希函数可以把给定的数据转换成固定长度的无规律数值。

1、将数据输入到哈希函数

2、输出的无规律数值就是“哈希值” 。哈希值虽然是数字，但多用十六进制来表示。

3、计算机同样适用0和1管理输入和输出的哈希值，因此哈希函数实际上是在计算机内部进行着某种运算的

哈希函数的特征

输出的哈希值数据长度不变
如果输入的数据相同，那么输出的哈希值也必定相同。
即使输入的数据相似，但哪怕它们只有一比特的差别，那么输出的哈希值也会有很大的差异。输入相似的数据并不会导致输出的哈希值也相似。
即使输入的两个数据完全不同，输出的哈希值也有可能是相同的，虽然出现这种情况的概率比较低。这种情况叫作“哈希冲突” 。
不可能从哈希值反向推算出原本的数据。
求哈希值的计算相对容易

说明

哈希函数的算法中具有代表性的是 MD5、SHA-1和 SHA-2 等，其中 SHA-2 是现在应用较为广泛的一个，而 MD5 和 SHA-1 存在安全隐患，不推荐使用。

不同算法的计算方式也会有所不同，比如 SHA-1 需要经过数百次的加法和移位运算才能生成哈希值。

本节所说的输入相同得到的哈希值也相同是在同一算法前提下，若哈希算法不同，则输出的哈希值也不同

应用案例

将用户输入的密码保存到服务器时也需要用到哈希函数，将用户输入的原始密码经过哈希函数，存储在服务器中，当用户输入密码后，与服务器上的哈希值进行比较，即便被第三者窃听，由于第五个特性，不可逆，也无法得知密码。使用哈希函数可以更安全地实现基于密码的用户认证

5-4 共享密钥加密

加密算法分为两种：

加密和解密使用相同密钥的**“共享密钥加密” **
加密和机密分别使用不同密钥的“公开密钥加密”

1、共享密钥加密指的是加密和解密使用相同密钥，因此这种算法也被称为“对称加密”

2、由于已经使用密钥对数据进行了加密，因此即便被第三者窃听也无关

3、问题

A将已加密的数据发送给B后，B不知道A使用的是什么密钥，因此A需要将密钥发送给B，这时第三者便可能窃听到发送的密钥，导致数据被窃听，这是共享密钥加密的最大问题。

说明

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

既然直接发送密钥有窃听的危险，那对密钥进行加密后再发送是否可行？这便回到了开始的问题，同样需要得到加密密钥的密钥。

找到可以把密钥安全送出的方法，这就是“密钥分配问题” 。为了解决这个问题，可以使用“密钥交换协议”和“公开密钥加密”两种方法

共享密钥加密，密钥的需求量会随着发送人数的增多而急剧增多，当人数为n时，需要密钥的数量为 $ n(n-1)/2 $

5-5 公开密钥加密

公开密钥加密是加密和解密使用不同密钥的一种加密方法。由于使用的密钥不同，所以这种算法也被称为“非对称加密” 。加密用的密钥叫作“公开密钥” ，解密用的叫作“私有密钥” 。

1、公开密钥加密流程

首先，由B生成公开密钥和私人密钥

B将公开密钥发送给A，A再将数据使用公开密钥进行加密，即便被加密的数据被X窃听，由于需要使用私人密钥进行机密，也无被窃听的风险

与共享密钥加密不同的是，公开密钥加密无密钥分配问题

2、在多人传输数据中，公开密钥加密相当方便

B将生成的公开密钥公布在网上，想要向B发送数据的人获得公开密钥后对要发送的内容进行加密，然后将已加密的数据发送给B，B通过私人密钥得到发送的数据

3、问题，公开密钥存在公开密钥可靠性问题和中间人攻击问题

当B将自己的公开密钥公布到网上时，第三者可将B的公开密钥替换为自己的公开密钥，A不会知道公开密钥由谁生成，也不会发现公开密钥已经被替换

A使用第三者的公开密钥加密后发送，这时，第三者便成功窃听到了A发送的数据

若第三者再使用B的公开密钥对A发送的数据进行加密，再将其发送给B，B便可得到A发送的数据。问题是这一整个过程B不会意识到数据已被窃听。这种通过中途替换公开密钥来窃听数据的攻击方法叫作“中间人攻击” （man-in-the-middle attack）。

说明

公开密钥加密的算法有RAS算法、椭圆曲线加密算法等，其中使用最为广泛的是RSA算法。

公开密钥的可靠性会出现问题，就是因为 A 无法判断收到的公开密钥是否来自 B。要想解决这个问题，就要用到之后会讲到的“数字证书”.

公开密钥加密还有一个问题，由于加密和解密都比较耗时，所以这种方法不适用于持续发送零碎数据的情况。要想解决这个问题，就要用到“混合加密” 。

公开密钥加密的算法需要满足如下条件：

可使用一个密钥对数据进行加密
可使用另一个密钥对数据解密
从一个密钥无法推算出另一个密钥

5-6 混合加密

共享密钥加密存在无法安全传输密钥的密钥分配问题，公开密钥加密又存在加密解密速度较慢和密钥可靠性的问题。结合这两种方法以实现互补的一种加密方法就是混合加密

在混合加密中，使用速度较快的共享密钥加密对数据进行加密，对于加密使用的密钥，使用没有密钥分配问题的公开密钥加密进行处理

混合加密的处理中，对于要发送的数据，使用速度较快的共享密钥进行加密，共享密钥的密钥使用B的公开密钥记性加密，经过传输后，B可使用私人密钥对共享密钥的加密密钥进行解密，然后再通过获得的共享密钥，对已加密的文件进行机密。

说明

混合加密在安全性和处理速度上都有优势。为网络提供通信安全的SSL协议使用了混合加密算法，SSL 是 Secure Sockets Layer（安全套接层），经升级后，命名为 TLS（Transport Layer Security，传输层安全），该协议称为SSL/TLS协议

5-7 迪菲 - 赫尔曼密钥交换

迪菲 - 赫尔曼（Diffie-Hellman）密钥交换是一种可以在通信双方之间安全交换密钥的方法。这种方法通过将双方共有的秘密数值隐藏在公开数值相关的运算中，来实现双方之间密钥的安全交换。

说明算法过程

1、A想和B交换密钥

2、假设有一种算法可将密钥P和S合并成密钥P-S

该合成方法有三个特征：

密钥之间可以合成，但不能分解。即使拥有密钥P和P-S，也无法获得密钥S
合成后的密钥还可以继续合成
密钥的合成结果与合成顺序无关，只与用了哪些密钥有关

3、在以上条件下，A将密钥发送给B

4、A和B分别使用自己的私人密钥对密钥P进行合并

5、A和B将已合并的密钥P-SA和P-SB发送给对方

6、A和B再使用私人密钥再次将接受的已合并的密钥进行合并，得到P-SA-SB，由于合并的密钥仅与参与的密钥有关，而和顺序无关，因此A和B得到的P-SA-SB相同，使用该密钥作为“加密密钥”和“解密密钥”

7、即便在通信过程中第三者窃听到了P，P-SA，P-SB，由于已合成的密钥无法分解，也无法获得P-SA-SB，因此这种方法是安全的

接下来用公式说明这种密钥交换法

1、使用P，G来表示公开密钥P，其中，P是相当大的素数，G是P对应的生成元中的一个

生成元的说明，根据博客生成元的意义

2的乘方结果中出现了1到12的全部整数。由于2具备上述性质，因此称为13的生成元。同样地，6、7和11也是生成元。

也就是说，P的生成元的乘方结果与1 ~ P-1的数字是一一对应的。正是因为具有这样的一一对应的关系，Alice才能够从1 ~ P-2范围中随机选择一个数字。

2、A生成素数P和生成元G，然后将其发送给B，即使P和G公开也没关系

3、A和B分别准备好秘密数字X和Y，且X,Y<=P-1

4、A和B分别进行如下计算，这可以理解为“合成”

5、然后A和B将计算的结果发送给对方

6、对方再利用接收的内容再次合成。对于A来说， $ {\left( {{G^Y}\bmod P} \right)^X}\bmod P = {G^{XY}}\bmod P $ ，对于B来说， $ {\left( {{G^X}\bmod P} \right)^Y}\bmod P = {G^{XY}}\bmod P $ ，因此二者相等，这就相当于获得了相同密钥

7、安全性问题。在通信过程中，即便第三者窃听到了P,G, $ {{G^Y}\bmod P} $ 和 $ {{G^X}\bmod P} $ ，也无法获得X和Y，因此整个过程是安全的。

说明

根据素数 P、生成元 G 和“ $ {{G^X}\bmod P} $ ”求出 X 的问题就是“离散对数问题” ，人们至今还未找到这个问题的解法，而迪菲 - 赫尔曼密钥交换正是利用了这个数学难题。

在通信中，通信双方仅交换一些公开信息便可实现密钥交换，事实上，二者并为交换密钥，而是生成了密钥，因此该方法又被叫作“迪菲 - 赫尔曼密钥协议” 。

5-8 消息认证码

消息认证码可以实现“认证”和“检测篡改”这两个功能。密文的内容在传输过程中可能会被篡改，这会导致解密后的内容发生变化，从而产生误会。消息认证码就是可以预防这种情况发生的机制。

1、正常情况下，假设A采用共享密钥加密将已加密的数据发送给B，B采用共享密钥对加密后的文件解密得到数据

2、问题：如果在A发送过程中，已加密的数据被第三方窃听，并且第三方进行恶意篡改，但是B收到密文后并未意识到这个问题

3、使用消息认证码的过程：A生成一个用于制作消息认证码的密钥，然后通过安全的方法将消息认证码的密钥发送给B

4、然后A利用密文和消息认证码的密钥生成一个值，这个值称为消息认证码，简称MAC（Message uthentication Code）

5、A将MAC和密文一块发送给B，B可通过密钥和密文来生成一个MAC，进行比对来查看是否被篡改

6、即使在这一过程中被第三者篡改，B通过消息认证码的密钥进行比对后，MAC的值将不同，可以意识到内容被篡改

说明

可将MAC想象为有密钥和密文构成的“哈希值”，计算MAC的算法有HMAC、OMAC、CMAC等。目前，HMAC的应用最为广泛。

加密仅仅是一个数值计算和处理的过程，所以即使密文被篡改了，也能够进行解密相关的计算。

如果原本的消息是很长的句子，那么它被篡改后意思会变得很奇怪，所以接收者有可能会发现它是被篡改过的。

但是，如果原本的消息就是商品编号等无法被人们直接理解的内容，那么解密后接收者便很难判断它是否被篡改。由于密码本身无法告诉人们消息是否被篡改，所以就需要使用消息验证码来检测。

补充

第三者是否可以对MAC进行篡改，使得密文看上去合理呢？

否定的，由于第三者没有MAC的密钥，因此即便他可以篡改 MAC，也无法让篡改后的密文变得合理。

这种方法也存在问题：由于A和B有相同的共享密钥和MAC的密钥，因此可生成完全相同的信息，因此无法证明原本的消息是 A 生成的还是 B 生成的。

若A为坏人，则可在发送消息后称“那条密文是B捏造的”；若B为坏人，则可准备好一条消息，称“这是A发送给我的”。因此要解决消息由哪方生成问题，需要“数字签名”。

5-9 数字签名

数字签名不仅可以实现消息认证码的认证和检测篡改功能，还可以预防事后否认问题的发生。由于在消息认证码中使用的是共享密钥加密，所以持有密钥的收信人也有可能是消息的发送者，这样是无法预防事后否认行为的。而数字签名是只有发信人才能生成的，因此使用它就可以确定谁是消息的发送者了。

1、数字签名的过程

A在要发送的消息上加上数字签名，数字签名仅能由A生成，发送到B后，B验证签名，确定由A发送，B仅能验证数字签名的正确性，而无法生成数字签名

2、数字签名生成过程，和公开密钥加密正好相反

首先，由A准备好公开密钥和私人密钥，将公开密钥发送给B

A使用私人密钥对数据进行加密，加密后的信息就是数字签名

使用私人密钥加密后的数字签名可以用公开密钥进行解密，但只能由私人密钥进行加密

说明

可发现，公开密钥任何人都可持有，并且经私人密钥加密后的数字签名，可由任何人解密。这种加密方法似乎没有意义，但是换个角度，该密文仅能由A（发送者）生成。

在数字签名中，只能由A生成的密文来作为签名使用，但是也有使用其他加密运算以外的计算方法来生成签名的情况。但和以上使用私人密钥加密，使用公开密钥解密的机制是相同的。

在公开密钥加密中，使用公开密钥加密，私人密钥解密；在数字签名中，使用私人密钥加密，公开密钥解密。因此，即使密钥使用顺序不同，得到的结果是相同的。但并不是所有公开密钥加密都有这个性质，RAS算法可以。

补充

公开密钥加密的加密和解密都比较耗时。在实际中，不会对消息直接加密，而是先求得消息的哈希值，再对哈希值进行加密，然后将其作为签名来使用。

虽然数字签名可以实现“认证” “检测篡改” “预防事后否认”三个功能，但也有一个问题，那就是无法确认这个公开密钥是否是A的。其根本原因在于使用公开密钥加密无法确定公开密钥的制作者是谁。收到的公开密钥上也没有任何制作者的信息。比如，第三者可自己生成公开密钥和私人密钥，然后将其发送给B，这时B可能以为是A的公开密钥，通信过程便出现了问题。

5-10 数字证书

“数字签名”无法保证公开密钥确实来自信息的发送者。因此，就算公开密钥被第三者恶意替换，接收方也不会注意到。因此需要使用数字证书来保证公开密钥的正确性。

1、A向认证中心（Certification Authority，CA）申请发行证书，证明公开密钥 $ P_A $ 确实由自己生成

2、认证中心保留着他们自己的公开密钥和私人密钥，A将公开密钥 $ P_A $ 和邮箱等个人信息发送给认证中心。

3、认证中心对资料进行确认后确定为A的资料，然后使用认证中心的私人密钥进行加密，根据A的资料生成数字签名，放到一个文件中发送给A

4、A将数字证书作为公开密钥发送给B

5、B先验证邮箱信息为A的邮箱信息，然后再从认证中心获得公开密钥，判断是否为认证中心的签名。

6、在确认了邮箱信息和数字证书的正确性后，B再从数字证书中获取A的公开密钥，由此A的公开密钥便被传送到了B

7、接下来验证是否有问题。若第三者直接将公开密钥发送给B，B没有必要信任以非证书形式收到的公开密钥。若B使用A的邮箱信息去认证中心申请数字证书，由于申请数字证书仅能使用自己的邮箱地址，因此无法获得A的证书

说明

通过数字证书，信息的接收者可以确认公开密钥的制作者。

还有一个问题，B怎么确认公开密钥 $ P_C $ 来自认证中心？

其实，本节中认证中心的公开密钥 $ P_C $ 是以数字证书的形式交付的，会有更高级别的认证中心对这个认证中心署名

因此，通过这个过程，便构成了认证中心树结构。最顶端的认证中心被称为“根认证中心” （root CA），其自身的正当性由自己证明，对根认证中心自身进行证明的证书为“根证书” 。如果根认证中心不被信任，整个组织就无法运转。因此根认证中心多为大型企业，或者与政府关联且已经取得了社会信赖的组织。

补充

在网站之间的通信中同样也要用到数字证书。只要能收到来自网站的含有公开密钥的证书，就能确认该网站未被第三者冒充。此处的证书叫作“服务器证书” ，同样由认证中心发行。

个人的证书会与他的邮箱信息相对应，而服务器证书与域名信息相对应。因此，网站域名和存储网站本身的服务器由同一个组织管理

数字证书就是像这样通过认证中心来担保公开密钥的制作者。这一系列技术规范被统称为“公钥基础设施” （Public Key Infrastructure，PKI）。

6 聚类

6-1 什么是聚类

相似的对象分为一组

聚类就是在输入为多个数据时，将“相似”的数据分为一组的操作。1 个组就叫作 1 个“簇” 。

如何定义“相似”

1、定义数据间的差距

根据数据类型不同，定义该数据是否“相似”的标准也不同。具体来说，就是要对两个数据之间的“差距”进行定义。

例如，每个学生学习成绩有语文、数学、英语，把每个学生都转换成“ （语文成绩 , 数学成绩 , 英语成绩） ”形式的数据后，就可以将两个数据（c1, m1, e1）和（c2, m2, e2）之间的差距定义为 $ (c_1-c_2)^2+(m_1-m_2)2+(e_1-e_2)^2 $ ，其中差距小的数据就互为“相似的数据” 。

2、符合条件的算法

在定义好数据间的差距后，聚类的方法也会有很多种。我们可以设定各种各样的条件，设定什么样的条件取决于进行聚类的目的。

6-2 k-means算法

k-means 算法是聚类算法中的一种，它可以根据事先给定的簇的数量进行聚类。

1、事先准备好的数据如下，差距定义为两点之间的距离，将簇的数量定为3

2、随机选择3个点作为簇的中心点

3、分别计算各个点离哪个中心点最近

4、因此，根据各个点离中心点的距离，3个簇的聚类便完成

5、计算各个簇的重心，然后将簇的中心点移动到该位置。完成后重新计算所有点到中心点的距离，重新分簇

6、重复执行“将数据分到相应的簇中”和“将中心点移到重心的位置” 这两个操作，直到中心点不再发生变化为止。

说明

k-means算法中，随着不断重复以上两个操作，中心点必会在某处收敛。

由于k-means算法需要事先设定好簇的数量，因此可事先对数据进行分析，或者不断测试得到合适的簇的数量。在k-means算法中，即便事先设定的簇的数量相同，但随机设置的初始中心点位置不同，所得的结果可能也不同，因此可通过不断测试初始中心点的位置来得到最合适的聚类结果。在以上例子中，若设置簇为2，初始中心点位置不同，结果也可能不同。

补充

除了k-means算法外，还有“层次聚类算法”可实现聚类，区别是层次聚类算法不需要事先设定簇的数量。

在层次聚类算法中，一开始每个数据都自成一类。也就是说，有 n 个数据就会形成n 个簇。然后重复执行“将距离最近的两个簇合并为一个”的操作 n-1 次。每执行 1 次，簇就会减少 1 个。执行 n-1 次后，所有数据就都被分到了一个簇中。在这个过程中，每个阶段的簇的数量都不同，对应的聚类结果也不同。只要选择其中最为合理的 1 个结果就好。

簇间距离的定义有“最短距离法” “最长距离法” “中间距离法”等多种算法。

7 其他算法

7-1 欧几里得算法

欧几里得算法（又称辗转相除法）用于计算两个数的最大公约数

首先先看下1112和695的最大公约数，将两个数进行分解后，找出共同的素数，便得到最大公约数（GCD）。

接下来介绍欧几里得算法的具体流程。

1、用较大数字对较小数字取mod运算

2、再用除数对所取的mod值取mod运算

3、不断进行如上操作，直到最后的结果为0

4、当所取mod值为0时，最后一次运算的除数便为二者的最大公约数

使用另一种方法来理解：

1、

2、1112和695一定是最大公约数的整数倍，由于现在我们已知二者的最大公约数为139，将1112划分为8个刻度，将695划分为5个刻度

3、同理，不断进行划分

说明

欧几里得算法，只需重复做除法便能求得最大公约数。这个算法最大的优势就在于即使两个数字再大，只要按照步骤进行操作就能高效地求得两者的最大公约数。

7-2 素数测试

素性测试是判断一个自然数是否为素数的测试。目前在加密技术中被广泛应用的 RSA 算法（5-5中的公开加密算法）就会用到大素数，因此“素性测试”在该算法中起到了重要的作用。

简单的测试方法：

对3599进行素数测试，由于3599的平方根为59.99，因此需要从2测试到59，若在测试中有mod为0，则不为素数。测试如下，可发现，3599不为素数

费马测试：

费马测试又称为概率性测试，即判断“这个数为素数的概率大不大”

先看下素数5有什么性质

可发现，小于5的数的5次方对5取模后，和原值相同，因此对于任意素数p，有

接下来测试113是否为素数，可判断113为素数

说明

若对于素数p，判断确定小于p的每个数，那么将会非常耗时，实际上，如果确认了几组和余数之后就能判断该数是素数的可能性非常高，那么大致就可以判定该数是素数了。

比如在 RSA 算法中，用于素性测试的是根据费马测试改进而来的“米勒 - 拉宾（Miller-Rabin）素性测试” 。用这个方法重复进行测试后，当数不是素数的概率小于 0.5时，就可以大致判断该数为素数。

补充

根据公式，若p为素数，则小于p的任意数n满足 $ {n^p}\bmod p = n $ 。但反过来，若满足以上条件，则p不一定为素数，在极低概率下存在所有n都满足以上公式的合数。这样的合数被称为“卡迈克尔数” （Carmichael numbers），也叫“绝对伪素数”。下面是一些绝对伪素数，数量很少