我的第一本算法书

窃听

假冒

篡改

事后否认

给需要保密的数据加密，加密后的数据称为"密文"

把密文恢复为原本数据的操作叫"解密"

对计算机来说，数据就是一串有意义的数字罗列(二进制串)，密文也是数字罗列，只不过它是计算机无法理解的无规律的数字罗列

加密就是用密钥对数据进行数值计算，把数据变成第三者无法理解的形式的过程

解密就是通过密钥进行数值计算，把密文恢复成原本数据的过程

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

哈希值虽然是数字，但多用十六进制表示

哈希函数的特征

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

恺撒加密、AES、DES、动态口令

共享密钥加密存在密钥被窃听的风险

加密用的密钥叫作"公开密钥"P，解密用的密钥叫作"私有密钥"S

RAS 算法、椭圆曲线加密算法

由接收方生成公开密钥和私有密钥，然后接收方把公开密钥发送给数据发送方，发送方用公开密钥进行加密，接收方用私有密钥解密

公开密钥和密文都是通过互联网传输的，因此可能会被 X 窃听。但是，使用公开密钥无法解密密文

公开密钥是不怕被人知道的，公开密钥可以被多个发送方获取；私有密钥不能被人知道，必须严密保管。

公开密钥加密加密和解密都比较耗时

公开密钥加密存在公开密钥可靠性的问题

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

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

假设A是发送方，B是接收方，A用共享密钥加密对数据加密，共享加密时的密钥设为A*，B事先生产公开密钥PB和私有密钥SB，B把PB发给A，A用PB对A*加密后把加密后的A*和密文发给B，B用SB解密A*，得到共享密钥，再用共享密钥解密密文

假设有一种密钥合成方法，将密钥P和密钥S合成为P-S,该方法有三个特征

设A为发送方，B为接收方，密钥P用两个整数p和g表示，p是一个很大的素数，g是p对应的生成元的中的一个，A准备好素数p和生成元g,p和g公开也没问题，A将p和g发给B；A和B各自准备神秘数字X和Y，X和Y必须小于p-2；合成过程：，A和B将自己的计算结果发给对方，然后A计算：，B计算：，最终A和B的结果都是, mod是求余操作

即便 X 窃听了整个通信过程，也无法用窃听到的数字计算出 A和 B 共有的数字。而且，X 也无法计算出保密数字 X 和 Y

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

消息认证码可以实现“认证”和“检测篡改” 这两个功能

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

A生成用于加密的密钥1，通过安全的方式发送给B，A生成一个用于制作消息认证码的密钥2，同样地发送给B；A使用密文和密钥2生成一个值，
这个值就是消息认证码MAC，A将密文和MAC发给B，B使用密文和密钥2生成MAC，对比两个MAC是否一致来确定密文是否被篡改；若一致，接下来，B 只需使用密钥1对密文进行解密即可

可以把 MAC 想象成是由密钥和密文组成的字符串的“哈希值”。计算MAC的算法有HMAC、 OMAC、 CMAC等

在消息认证码中使用的是共享密钥加密，所以持有密钥的收信人也有可能是消息的发送者，这样是无法预防事后否认行为的

使用 MAC 时，生成的一方和检测的一方持有同样的密钥，所以不能确定 MAC 由哪方生成。这个问题可以用数字签名来解决

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

数字签名是只有发信人才能生成的，因此使用它就可以确定谁是消息的发送者了

A要给B发送消息，在发送前A给消息加上数字签名，数字签名只能由A生成；B可以验证数字签名的正确性，但无法生成数字签名

公开密钥加密中，加密使用的是公开密钥P，解密使用的是私有密钥S，数字签名的生成使用的是公开密钥加密，然而，过程恰恰相反：用私有密钥生成签名、用公开密钥验证签名

首先由 A准备好需要发送的消息、私有密钥和公开密钥。由消息的发送者来准备这两个密钥，这一点与公开密钥加密有所不同；
A将公开密钥发送给 B；A使用私有密钥加密消息。加密后的消息就是数字签名，A将消息和签名都发送给了B；B使用公开密钥对密文（签名）进行解密，B 对解密后的消息进行确认，看它是否和收到的消息一致

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

数字签名可以实现“认证”“检测篡改”“预防事后否认” 三个功能

缺陷：使用公开密钥加密无法确定公开密钥的制作者是谁，收到的公开密钥上也没有任何制作者的信息。因此，公开密钥有可能是由某个冒充 A 的人生成的

“公开密钥加密”和“数字签名” 无法保证公开密钥确实来自信息的发送者,通过数字证书，信息的接收者可以确认公开密的制作者

A持有公开密钥PA和私有密钥SA，A首先向认证中心（CA）申请发行证书，证明PA确实由自己生成；A将PA和包含邮箱信息的个人资料发送给认证中心，认证中心有自己的PC和SC，认证中心确定A的信息后，使用SC对A的资料生成数字签名，认证中心将数字签名和资料放进同一个文件，这个文件就是A的数字证书，CA将数字证书发给A，A将作为公开密钥的数字证书发给B，CA将认证中心的PC发给B，B利用PC对证书中的签名进行验证，B确认了证书使用认证中心发的，且邮件地址是A的后，获得公开密钥PA

认证中心的公开密钥 PC 是以数字证书的形式交付的，会有更高级别的认证中心对这个认证中心署名，最高级别的认证中心是"根认证中心"

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

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

初始聚类中心不同，聚类结果不同

欧几里得算法(辗转相除法)用于计算两个数的最大公约数GCD

先用大数作为被除数，小数作为除数，求出余数，然后余数和除数中小的数当作除数，大的数当作被除数，迭代计算，直到余数为0，此时的除数就是原始两个数字的最大公约数

素数就是只能被1和其本身整除，且大于1的自然数；素性测试就是判断一个自然数是不是素数

假如判断3599是不是素数：简单的方法便是将3599 按顺序除以比 2 大的数字，看是否能被整除，由于3599 的平方根为59.99…，所以只需要除以从2到59的数字，如果有能整除的，那么3599就不是素数；3599能被 59整除。也就是说，3599并不是素数。如果一个数非常大，这种方法会很慢

费马测试被称为概率性素性测试，它判断的是“某个数是素数的概率大不大”。

费马小定理：对于素数p, 若n<p,则有n**p mod p = n，根据是否满足费马小定理来判断一个数是不是素数的方法就是费马测试

确认 n 和余数一致的次数越多，需要判断的数确实为素数的可能性就越大

如果p是素数，那么所有比p小的数n都满足n**p mod p ＝ n 这个条件。但反过来，即使所有n都满足条件， p也有可能不是素数，因为在极低概率下会出现所有n都满足条件的合数，这样的合数叫作"卡迈克尔数"，也叫"绝对伪素数"，这种数字非常少

AKS算法：在输入规模的多项式时间内进行（非概率意义，而是决定性的）素性测试，虽说是在多项式时间内但该算法的计算次数仍然较多，所以费马测试这样的高速算法更为实用

网页排名（ PageRank，也叫作佩奇排名）是一种在搜索网页时对搜索结果进行排序的算法

网页排名就是利用网页之间的链接结构计算出网页价值的算法

假设有n个圆盘，时间复杂度为

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

算法是严密的

程序是以计算机能够理解的编程语言编写而成，可以在计算机上运行
算法是以人类能够理解的方式描述的，用于编写程序前

同一个算法，编程语言不同，写出来的程序不同；相同的编程语言，不同的人写出来的程序也不同

算法的时间复杂度是一个可以描述算法运行时间的函数，常用大O符号来表述，读作Order，大O表示法只取高阶项，忽略其他项

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

根据使用目的选择合适的数据结构，可以提高内存的利用率

链表中的数据呈线性排列

在链表中，数据一般是分散存储于内存中，无须存储在连续空间内

循环链表：一般链表尾部没有指针，若尾部使用指针并指向链表头部数据，将链表变成环形，即为循环链表

双向链表：每个数据有两个指针，分别指向前后数据

数组中数据呈线性排列

数组中数据按顺序存储在内存的连续空间内

栈中数据呈线性排列，只能访问最新添加的数据

往栈中添加数据的操作叫"入栈push"，从栈中取出数据的操作叫"出栈pop"

栈中最后添加的数据最先被取出，即"后进先出", Last In First Out:LIFO

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

在只需要访问最新数据时使用栈比较方便

队列中数据呈线性排列

添加数据叫"入队"，删除数据叫"出队"

队列中最先进去的数据最先被取出，即"先进先出",First In First Out, FIFO

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

广度优先搜索：通常选择最早的数据作为候补顶点，在候补顶点的管理上可以使用队列

哈希表存储的是由键和值组成的数据，键是数据的标识符，值是数据的内容

开辟N个储存单元，通过哈希函数计算数据的键，即哈希值，将哈希值除以N取余数，即"mod运算"，将数据写入余数对应的储存单元中

冲突

可以利用哈希函数快速访问数组中的目标数据

堆是一种图的树形结构，被用于实现"优先队列"，优先队列可以自由添加数据，但取出数据时要从最小值开始按顺序取出

在堆的树形结构中，各个顶点称为"结点"(node)，数据存储在结点中

堆的性质

采用了图的树形结构，每个结点最多两个子节点

二叉查找树的性质

添加数据

删除数据

查找数据O(logn)：从二叉查找树的顶端结点开始往下查找。和添加数据时一样，把要查找的值和结点中的值进行比较，小于该结点的值则往左移，大于则往右移。

B树

重复"从序列右边开始比较相邻两个数字的大小，根据比较结果交换两个数字的位置"这一操作

想象一个天平放在数组最右边两个数字上，比较它们并根据结果交换位置，将天平左移一位，继续比较，直到天平移到最左边两个数字，比较并交换后最左边数字即为最小值，此为"一轮"。接着将天平移到最右边两个数字，重复此操作，比较K轮后最左边K个数字已经排好序，无需再次比较

冒泡排序中，第一轮需要比较n-1次，第二轮需要比较n-2次，第n-1轮需要比较1次，总的比较次数为n^2,即冒泡排序的时间复杂度O(n^2)

重复"从待排序数组中寻找最小值，将其与序列最左边的数字进行交换"这一操作的算法，寻找最小值时采用线性查找

使用线性查找寻找最小值后与最左边数字交换，此为"一轮"；在余下数据中寻找最小值，将其与左边第二个数字交换，重复下去

选择排序使用线性查找寻找最小值，第一轮需要比较n-1个数字,第2轮需要比较n-2个数字,第n-1轮需要比较1个数字，故选择排序的时间复杂度O(n^2)

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

第一轮操作就是假设最左边的一个数字已经排好序，然后从待排序中取出最左边的数字，将它与左边已排好序的数字比较，根据比较结果交换位置，若取出的数字比左边已排序的数字都大，则不须交换

在插入排序中，需要将取出的数据与其左边的数字进行比较，如果左边的数字更小，就不需要继续比较，本轮操作到此结束。

如果取出的数字比左边已归位的数字都要小，就必须不停地比较大小，交换数字，直到它到达整个序列的最左边为止

在最糟糕的情况下，第 2 轮需要操作 1 次，第 3 轮操作 2 次……第 n 轮操作 n-1次，所以插入排序时间复杂度为O(n^2)

堆排序一开始需要将 n 个数据存进堆里，所需时间为 O(nlogn)

利用堆进行排序

归并排序算法会把序列分成长度相同的两个子序列，当无法继续往下分时（也就是每个子序列中只有一个数据时），就对子序列进行归并

归并指的是把两个排好序的子序列合并成一个有序序列。该操作会一直重复执行，直到所有子序列都归并为一个整体为止

比较子序列中剩下的首位数字

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

[ 比基准值小的数 ] 基准值 [ 比基准值大的数 ]

接着，对两个“[ ]” 中的数据进行排序之后，整体的排序便完成了。对“[ ]” 里面的数据进行排序时同样也会使用快速排序。

分治法+递归：递归结束条件：只有在[]里只剩一个数字的时候，排序才算完成

分割子序列时需要选择基准值，如果每次选择的基准值都能使得两个子序列的长度为原本的一半，那么快速排序时间复杂度为 O(nlogn)

基准值选择

从头开始不断地按顺序检查数据，即便数据没有按顺序存储。线性查找的时间复杂度O(n)

只能查找已经排好序的数据，二分查找的时间复杂度O(logn)

二分查找通过比较数组中间的数据与目标数据的大小，可以得知目标数据是在数组的左边还是右边。
因此，比较一次就可以把查找范围缩小一半，查找范围内只剩一个数据时查找结束。

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

给边加上一个值。这个值叫作边的“权重”或者“权”，加了权的图被称为加权图

有向图，加权有向图

广度优先搜索优先从离起点近的顶点开始搜索

起点的子节点作为候补顶点，从候补顶点中选出一个顶点，优先选择最早成为候补的那个顶点，如果多个顶点同时成为候补顶点，那么可以随机选择一个作为顶点，由近及远进行广泛的搜索，直到找到目标顶点

广度优先搜索的候补顶点是用先入先出方式来管理的，因此可以使用“队列”进行管理

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

深度优先搜索优先选择最新成为候补的点，如果几个顶点同时成为候补，那么可以从中随意选择一个

深度优先搜索的候补顶点是用后入先出方式来管理的，因此可以使用“栈”进行管理

贝尔曼 - 福特（ Bellman-Ford）算法是一种在图中求解最短路径问题的算法

最短路径问题就是在加权图指定了起点和终点的前提下，寻找从起点到终点的路径中权重总和最小的那条路径

将图的顶点数设为 n、边数设为 m，贝尔曼-福特算法的时间复杂度为O(nm)

贝尔曼-福特算法可以用于无向图、有向图、边权为负的图

首先设置各个顶点的初始权重 ：起点为 0，其他顶点为无穷大；从所有的边中选出一条边，分别计算这条边从一端到另一端的权重，计算方法是“顶点原本的权重＋边的权重”；如果计算结果小于顶点的值，就更新这个值，更新时需要记录计算的是从哪个顶点到该顶点的路径；对所有的边都执行同样的操作
更新完所有的边后，第1轮更新就结束了。接着，重复对所有边的更新操作，直到权重不能被更新为止

最短路径问题

首先设置各个顶点的初始权重： 起点为 0，其他顶点为无穷大；从起点出发，寻找可以从目前所在的顶点直达且尚未被搜索过的顶点，将它们设为下一步的候补顶点；计算各个候补顶点的权重。计算方法是“目前所在顶点的权重＋目前所在顶点到候补顶点的权重”，如果计算结果小于候补顶点的值，就更新这个
值；从候补顶点中选出权重最小的顶点，将可以从新顶点直达的顶点设为新的候补顶点，用相同的方法计算各个候补顶点的权重，从候补顶点中选出权重最小的顶点；重复执行同样的操作直到到达终点

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

将图的顶点数设为 n、边数设为 m，那么如果事先不进行任何处理，该狄克斯特拉算法的时间复杂度就是 O(n2)。如果对数据结构进行优化，那么时间复杂度就会变为O(m +nlogn)

如果图中含有负数权重，狄克斯特拉算法可能会无法得出正确答案

狄克斯特拉算法会从离起点近的顶点开始，按顺序求出起点到各个顶点的最短路径。也就是说，一些离终点较远的顶点的最短路径也会被计算出来，但这部分其实是无用的；A* 就会预先估算一个值，并利用这个值来省去一些无用的计算