我的第一本算法书
前言
- 使用不同的算法解决同一个问题时，就算得到的结果是一样的，算法之间的性质也有很大的差异。比如，某个算法的运行时间很短，但需要占用大量内存；而另一个算法运行时间较长，但内存资源占用较少。学习各种算法可以使我们在编程时有更多的选择。成为优秀程序员的必要条件之一，就是可以根据应用场景选择最合适的算法。
- 要想执行高效的算法，还需要使用合适的数据结构。
序章 算法的基本知识
- 算法和程序有些相似，区别在于程序是以计算机能够理解的编程语言编写而成的，可以在计算机上运行，而算法是以人类能够理解的方式描述的，用于编写程序之前。
- 只解决这一个问题很简单，但是算法是可以应对任意输入的计算步骤，所以必须采用通用的描述。
- 计算机擅长高速执行一些基本命令，但无法执行复杂的命令。此处的“基本命令”指的是“做加法”或者“在指定的内存地址上保存数据”等。
- 仅仅是对50个数字进行排序，若使用全排列算法，就算花费宇宙年龄的109倍时间也得不出答案
- 为了在第1轮找到最小的数字，需要从左往右确认数列中的数字，只要查询n个数字即可
0-2 运行时间的计算方法
- 了解输入数据的量和运行时间之间的关系
- 我们不光要理解不同算法在运行时间上的区别，还要了解根据输入数据量的大小，算法的运行时间具体会产生多大的变化。
- 所以在这里，我们使用“步数”来描述运行时间。“1步”就是计算的基本单位。通过测试“计算从开始到结束总共执行了多少步”来求得算法的运行时间。
- O这个符号的意思是“忽略重要项以外的内容”，读音同Order。O（n2）的含义就是“算法的运行时间最长也就是n2的常数倍”
第1章 数据结构
- 数据存储于内存时，决定了数据顺序和位置关系的便是“数据结构”。
- 因为数据都是以字典顺序排列的，所以它们是有“结构”的。
- 将数据存储于内存时，根据使用目的选择合适的数据结构，可以提高内存的利用率。
1-2 链表
- 链表是数据结构之一，其中的数据呈线性排列。在链表中，数据的添加和删除都较为方便，就是访问比较耗费时间。
- 在链表中，数据一般都是分散存储于内存中的，无须存储在连续空间内。
- 如果想要添加数据，只需要改变添加位置前后的指针指向就可以
- 双向链表存在两个缺点：一是指针数的增加会导致存储空间需求增加；二是添加和删除数据时需要改变更多指针的指向。
1-3 数组
- 在数组中，访问数据十分简单，而添加和删除数据比较耗工夫。
- 数据按顺序存储在内存的连续空间内。
- 由于数据是存储在连续空间内的，所以每个数据的内存地址（在内存上的位置）都可以通过数组下标算出，我们也就可以借此直接访问目标数据（这叫作“随机访问”）。
- 如果想在任意位置上添加或者删除数据，数组的操作就要比链表复杂多了。
- 在链表和数组中，数据都是线性地排成一列。在链表中访问数据较为复杂，添加和删除数据较为简单；而在数组中访问数据比较简单，添加和删除数据却比较复杂。
1-4 栈
- 栈也是一种数据呈线性排列的数据结构，不过在这种结构中，我们只能访问最新添加的数据。栈就像是一摞书，拿到新书时我们会把它放在书堆的最上面，取书时也只能从最上面的新书开始取。
- 像栈这种最后添加的数据最先被取出，即“后进先出”的结构，我们称为Last In First Out，简称LIFO。
1-5 队列
- 队列中添加和删除数据的操作分别是在两端进行的
- 从队列中取出（删除）数据时，是从最下面，也就是最早入队的数据开始的。
- 像队列这种最先进去的数据最先被取来，即“先进先出”的结构，我们称为First In First Out，简称FIFO。
1-6 哈希表
- 哈希表存储的是由键（key）和值（value）组成的数据。
- 一般来说，我们可以把键当成数据的标识符，把值当成数据的内容。
- 数据量越多，线性查找耗费的时间就越长。由此可知：由于数据的查询较为耗时，所以此处并不适合使用数组来存储数据。
- 将得到的哈希值除以数组的长度5，求得其余数。这样的求余运算叫作“mod运算”。
- 使用链表在已有数据的后面继续存储新的数据
- 在存储数据的过程中，如果发生冲突，可以利用链表在已有数据的后面插入新数据来解决冲突。这种方法被称为“链地址法”。
- 在哈希表中，我们可以利用哈希函数快速访问到数组中的目标数据。如果发生哈希冲突，就使用链表进行存储。这样一来，不管数据量为多少，我们都能够灵活应对。
1-7 堆
- 堆是一种图的树形结构，被用于实现“优先队列”（priority queues）
- 堆中的每个结点最多有两个子结点。树的形状取决于数据的个数。另外，结点的排列顺序为从上到下，同一行里则为从左到右。
- 在堆中存储数据时必须遵守这样一条规则：子结点必定大于父结点。
- 如果父结点大于子结点，则不符合上文提到的规则，因此需要交换父子结点的位置。
- 从堆中取出数据时，取出的是最上面的数据。这样，堆中就能始终保持最上面的数据最小。
- 假设数据量为n，根据堆的形状特点可知树的高度为log2n，那么重构树的时间复杂度便为O（logn）。
- 如果需要频繁地从管理的数据中取出最小值，那么使用堆来操作会非常方便。
1-8 二叉查找树
- 二叉查找树（又叫作二叉搜索树或二叉排序树）是一种数据结构，采用了图的树形结构
- 二叉查找树有两个性质。第一个是每个结点的值均大于其左子树上任意一个结点的值。
- 二叉查找树的最小结点要从顶端开始，往其左下的末端寻找
- 二叉查找树的最大结点要从顶端开始，往其右下的末端寻找。
- 首先，从二叉查找树的顶端结点开始寻找添加数字的位置。将想要添加的1与该结点中的值进行比较，小于它则往左移，大于它则往右移。
- 如果需要删除的结点没有子结点，直接删掉该结点即可。
- 如果需要删除的结点只有一个子结点，那么先删掉目标结点……
- 然后在被删除结点的左子树中寻找最大结点……
- 删除9的时候，我们将“左子树中的最大结点”移动到了删除结点的位置上，但是根据二叉查找树的性质可知，移动“右子树中的最小结点”也没有问题。
- 像这种子结点数可以自由设定，并且形状均衡的树便是B树。
第2章 排序
- 排序就是将输入的数字按照从小到大的顺序进行排列。
- 为了便于讲解，同一个例子中不会出现相同的数字，但实际上，即使有相同的数字，算法依然可以正常运行
2-2 冒泡排序
- 冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字的位置”这一操作的算法。
- 通过这一系列操作，序列中最小的数字就会移动到最左边。
- 冒泡排序的时间复杂度为O（n2）。
2-3 选择排序
- 选择排序就是重复“从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换”这一操作的算法。
- 选择排序的时间复杂度也和冒泡排序的一样，都为O（n2）。
2-4 插入排序
- 插入排序的思路就是从右侧的未排序区域内取出一个数据，然后将它插入到已排序区域内合适的位置上。
- 所以时间复杂度和冒泡排序的一样，都为O（n2）。
2-5 堆排序
- 堆排序的特点是利用了数据结构中的堆。
- 在堆中存储所有的数据，并按降序来构建堆。
- 从降序排列的堆中取出数据时会从最大的数据开始取，所以将取出的数据反序输出，排序就完成了。
- 整体来看堆排序的时间复杂度为O（nlogn）。
2-6 归并排序
- 归并排序算法会把序列分成长度相同的两个子序列，当无法继续往下分时（也就是每个子序列中只有一个数据时），就对子序列进行归并。归并指的是把两个排好序的子序列合并成一个有序序列。
- 合并这种含有多个数字的子序列时，要先比较首位数字，再移动较小的数字。
- 总的运行时间为O（nlogn）
2-7 快速排序
- 快速排序算法首先会在序列中随机选择一个基准值（pivot），然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别，再将其排列成以下形式。 [比基准值小的数] 基准值 [比基准值大的数]
- 快速排序是一种“分治法”。它将原本的问题分成两个子问题（比基准值小的数和比基准值大的数），然后再分别解决这两个问题。
- 分割子序列时需要选择基准值，如果每次选择的基准值都能使得两个子序列的长度为原本的一半，那么快速排序的运行时间和归并排序的一样，都为O（nlogn）。
第3章 数组的查找
- 线性查找的操作很简单，只要在数组中从头开始依次往下查找即可。
- 若数据量为n，线性查找的时间复杂度便为O（n）。
3-2 二分查找
- 二分查找也是一种在数组中查找数据的算法。和3-1节讲到的线性查找不同，它只能查找已经排好序的数据。
- 二分查找的时间复杂度为O（logn），与线性查找的O（n）相比速度上得到了指数倍提高（x=log2n，则n=2x）。
第4章 图的搜索
- 由顶点和连接每对顶点的边所构成的图形就是图。
- 这个值叫作边的“权重”或者“权”，加了权的图被称为“加权图”。没有权的边只能表示两个顶点的连接状态，而有权的边就可以表示顶点之间的“连接程度”。
- 当我们想在路线图中表示该路线只能单向行驶时，就可以给边加上箭头，而这样的图就叫作“有向图”。
- 使用有向图还可以设置非对称的权重。
- 根据搜索的顺序不同，图的搜索算法可分为“广度优先搜索”和“深度优先搜索”这两种。
4-2 广度优先搜索
- 广度优先搜索会优先从离起点近的顶点开始搜索。
- 优先选择最早成为候补的那个顶点，如果多个顶点同时成为候补，那么可以随意选择其中一个。
- 此处，候补顶点是用“先入先出”（FIFO）的方式来管理的，因此可以使用“队列”这个数据结构。
- 候补顶点是用“先入先出”（FIFO）的方式来管理的，因此可以使用“队列”这个数据结构。
- 广度优先搜索的特征为从起点开始，由近及远进行广泛的搜索。因此，目标顶点离起点越近，搜索结束得就越快。
4-3 深度优先搜索
- 深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条候补路径。
- 候补顶点是用“后入先出”（LIFO）的方式来管理的，因此可以使用“栈”这个数据结构。
- 此处，候补顶点是用“后入先出”（LIFO）的方式来管理的，因此可以使用“栈”这个数据结构。
- 广度优先搜索选择的是最早成为候补的顶点，因为顶点离起点越近就越早成为候补，所以会从离起点近的地方开始按顺序搜索；而深度优先搜索选择的则是最新成为候补的顶点，所以会一路往下，沿着新发现的路径不断深入搜索。
4-4 贝尔曼-福特算法
- 贝尔曼-福特（Bellman-Ford）算法是一种在图中求解最短路径问题的算法。最短路径问题就是在加权图指定了起点和终点的前提下，寻找从起点到终点的路径中权重总和最小的那条路径。
- 首先设置各个顶点的初始权重：起点为0，其他顶点为无穷大（∞）。这个权重表示的是从A到该顶点的最短路径的暂定距离。随着计算往下进行，这个值会变得越来越小，最终收敛到正确的数值。
- 如果计算结果小于顶点的值，就更新这个值。
- 所有顶点的权重都不再更新，操作到此为止
- 贝尔曼也因为提出了该算法中的一个重要分类“动态规划”而被世人所熟知。
4-5 狄克斯特拉算法
- 狄克斯特拉（Dijkstra）算法也是求解最短路径问题的算法，使用它可以求得从起点到终点的路径中权重总和最小的那条路径路径。
- 寻找可以从目前所在的顶点直达且尚未被搜索过的顶点
- 目前所在顶点的权重+目前所在顶点到候补顶点的权重
- 从候补顶点中选出权重最小的顶点
- 因此，有负数权重时不能使用狄克斯特拉算法。
4-6 A*算法
- A*就会预先估算一个值，并利用这个值来省去一些无用的计算。
- 此处我们用的是将顶点到终点的直线距离四舍五入后的值。
- 这里我们只知道终点所在位置，不知道该如何通往终点，所以使用了直线距离
- 如果我们能得到一些启发信息，即各个顶点到终点的大致距离（这个距离不需是准确的值）我们就能使用A*算法。当然，有时这类信息是完全无法估算的，这时就不能使用A*算法。
第5章 安全算法
- 为了应对第一个问题“窃听”，我们会使用 “加密”技术。 为了应对第二个问题“假冒”，我们会使用“消息认证码”（下图左）或“数字签名”（下图右）技术。
5-2 加密的基础知识
- 加密就是数据经过某种运算后，变成计算机无法理解的数的过程
- 反过来，解密就是像下图这样，通过密钥进行数值计算，把密文恢复成原本数据的过程。
- 像这样，将数据变成第三者的计算机无法理解的形式，然后再将其恢复成原本数据的一系列操作就是加密技术。
5-3 哈希函数
- 哈希函数可以把给定的数据转换成固定长度的无规律数值。
- 为了便于理解，我们可以把哈希函数想像成搅拌机
- 哈希值虽然是数字，但多用十六进制来表示。
- 第一个特征是输出的哈希值数据长度不变。
- 第二个特征是如果输入的数据相同，那么输出的哈希值也必定相同。
- 第三个特征是即使输入的数据相似，但哪怕它们只有一比特的差别，那么输出的哈希值也会有很大的差异。输入相似的数据并不会导致输出的哈希值也相似。
- 第五个特征是不可能从哈希值反向推算出原本的数据。输入和输出不可逆这一点和加密有很大不同。
- 最后一个特征是求哈希值的计算相对容易。
- 哈希函数的算法中具有代表性的是MD5[插图]、SHA-1[插图]和SHA-2等。其中SHA-2是现在应用较为广泛的一个，而MD5和SHA-1存在安全隐患，不推荐使用。
5-4 共享密钥加密
- 加密和解密都使用相同密钥的“共享密钥加密”和分别使用不同密钥的“公开密钥加密”
- 共享密钥加密是加密和解密都使用相同密钥的一种加密方式。由于使用的密钥相同，所以这种算法也被称为“对称加密”。
- 实现共享密钥加密的算法有凯撒密码、AES、DES、动态口令等，其中AES的应用最为广泛。
- 但是，该密钥也有可能会被X窃听。这样一来，X也可以使用密钥对密文进行解密了。
- 要想解决这个问题，可以使用“密钥交换协议”和“公开密钥加密”两种方法。
5-5 公开密钥加密
- 公开密钥加密是加密和解密使用不同密钥的一种加密方法。由于使用的密钥不同，所以这种算法也被称为“非对称加密”。加密用的密钥叫作“公开密钥”，解密用的叫作“私有密钥”。
- A将密文发送给B, B再使用私有密钥对密文进行解密。这样，B就得到了原本的数据。
- 实现公开密钥加密的算法有RAS算法、椭圆曲线加密算法等，其中使用最为广泛的是RSA算法。
- 公开密钥和密文都是通过互联网传输的，因此可能会被X窃听。但是，使用公开密钥无法解密密文，因此X也无法得到原本的数据。
- 公开密钥加密存在公开密钥可靠性的问题。
- 于是公开密钥PX传到了A那里。由于公开密钥无法显示自己是由谁生成的，所以A不会发现自己收到的公开密钥已经被人替换。
- 这种通过中途替换公开密钥来窃听数据的攻击方法叫作“中间人攻击”（man-in-the-middle attack）。
- 公开密钥加密还有一个问题，那就是加密和解密都比较耗时，所以这种方法不适用于持续发送零碎数据的情况。要想解决这个问题，就要用到“混合加密”。
5-6 混合加密
- 共享密钥加密存在无法安全传输密钥的密钥分配问题，公开密钥加密又存在加密解密速度较慢的问题。结合这两种方法以实现互补的一种加密方法就是混合加密。
- 在混合加密中，要用处理速度较快的共享密钥加密对数据进行加密。不过，加密时使用的密钥，则需要用没有密钥分配问题的公开密钥加密进行处理。
5-7 迪菲-赫尔曼密钥交换
- 迪菲-赫尔曼（Diffie-Hellman）密钥交换是一种可以在通信双方之间安全交换密钥的方法。这种方法通过将双方共有的秘密数值隐藏在公开数值相关的运算中，来实现双方之间密钥的安全交换。
- 第一，即使持有密钥P和合成的密钥P-S，也无法把密钥S单独取出来。
- 第三，密钥的合成结果与合成顺序无关，只与用了哪些密钥有关。
- 这个密钥将作为“加密密钥”和“解密密钥”来使用
- 但是，X无法用自己窃听到的密钥合成出P-SA-SB，因此这种交换方式是安全的。
- 根据素数P、生成元G和“GX mod P”求出X的问题就是“离散对数问题”，人们至今还未找到这个问题的解法，而迪菲-赫尔曼密钥交换正是利用了这个数学难题。
5-8 消息认证码
- 消息认证码可以实现“认证”和“检测篡改”这两个功能。
- 这个由密钥和密文生成的值就是消息认证码，以下简称为MAC（Message Authentication Code）。
- 和A一样，B也需要使用密文和密钥来生成MAC。经过对比，B可以确认自己计算出来的7f05和A发来的7f05一致。
- 我们可以把MAC想象成是由密钥和密文组成的字符串的“哈希值”。计算MAC的算法有HMAC[插图]、OMAC[插图]、CMAC[插图]等。目前，HMAC的应用最为广泛。
- 加密仅仅是一个数值计算和处理的过程，所以即使密文被篡改了，也能够进行解密相关的计算。
- 使用MAC时，生成的一方和检测的一方持有同样的密钥，所以不能确定MAC由哪方生成。这个问题可以用下一节将会讲到的“数字签名”来解决。
5-9 数字签名
- 数字签名不仅可以实现消息认证码的认证和检测篡改功能，还可以预防事后否认问题的发生
- 数字签名的生成使用的是公开密钥加密。
- 公开密钥加密中，加密使用的是公开密钥P，解密使用的是私有密钥[插图]。任何人都可以使用公开密钥对数据进行加密，但只有持有私有密钥的人才能解密数据。然而，数字签名却是恰恰相反的。
- A使用私有密钥加密消息。加密后的消息就是数字签名。
- 公开密钥加密的加密和解密都比较耗时。为了节约运算时间，实际上不会对消息直接进行加密，而是先求得消息的哈希值，再对哈希值进行加密，然后将其作为签名来使用
5-10 数字证书
- “公开密钥加密”和“数字签名”无法保证公开密钥确实来自信息的发送者。因此，就算公开密钥被第三者恶意替换，接收方也不会注意到。不过，如果使用本节讲解的数字证书，就能保证公开密钥的正确性。
- A首先需要向认证中心（Certification Authority, CA）申请发行证书，证明公开密钥PA确实由自己生成。
- 认证中心对收到的资料进行确认，判断其是否为A本人的资料。确认完毕后，认证中心使用自己的私有密钥SC，根据A的资料生成数字签名。
- 认证中心将生成的数字签名和资料放进同一个文件中
- 认证中心是管理数字证书的组织机构。原则上谁都可以成为认证中心，所以认证中心的数量也比较多，但建议在经过政府审查的大型企业机构进行申请，这些机构更令人放心。
- 接着，B获取了认证中心的公开密钥。
- 通过数字证书，信息的接收者可以确认公开密钥的制作者。
- 实际上，认证中心的公开密钥PC是以数字证书的形式交付的，会有更高级别的认证中心对这个认证中心署名
- 最顶端的认证中心被称为“根认证中心”（root CA），其自身的正当性由自己证明。对根认证中心自身进行证明的证书为“根证书”。如果根认证中心不被信任，整个组织就无法运转。因此根认证中心多为大型企业，或者与政府关联且已经取得了社会信赖的组织。
- 数字证书就是像这样通过认证中心来担保公开密钥的制作者。这一系列技术规范被统称为“公钥基础设施”（Public Key Infrastructure, PKI）。
第6章 聚类
- 聚类就是在输入为多个数据时，将“相似”的数据分为一组的操作。
6-2 k-means算法
- k-means算法是聚类算法中的一种，它可以根据事先给定的簇的数量进行聚类。
- 计算各个数据分别和3个中心点中的哪一个点距离最近。
- 计算各个簇中数据的重心，然后将簇的中心点移动到这个位置。
- 重新计算距离最近的簇的中心点，并将数据分到相应的簇中。
- 重复执行“将数据分到相应的簇中”和“将中心点移到重心的位置”这两个操作，直到中心点不再发生变化为止。
- k-means算法中，随着操作的不断重复，中心点的位置必定会在某处收敛
- 由于k-means算法需要事先确定好簇的数量，所以设定的数量如果不合理，运行的结果就可能会不符合我们的需求。
- 即使簇的数量相同，只要随机设置的中心点最初的位置不同，聚类的结果也会产生变化。因此，我们可以通过改变随机设定的中心点位置来不断尝试k-means算法，再从中选择最合适的聚类结果。
- 在层次聚类算法中，一开始每个数据都自成一类。也就是说，有n个数据就会形成n个簇。然后重复执行“将距离最近的两个簇合并为一个”的操作n-1次。每执行1次，簇就会减少1个。执行n-1次后，所有数据就都被分到了一个簇中。在这个过程中，每个阶段的簇的数量都不同，对应的聚类结果也不同。只要选择其中最为合理的1个结果就好。
第7章 其他算法
- 欧几里得算法（又称辗转相除法）用于计算两个数的最大公约数，被称为世界上最古老的算法。
- 先对两个数字因式分解，找出共同的素数，然后求出最大公约数（GCD）。这样就能求出1112和695的最大公
- 余数为0时，最后一次运算中的除数139就是1112和695的最大公约数。
7-2 素性测试
- 素性测试是判断一个自然数是否为素数的测试。素数（prime number）就是只能被1和其自身整除，且大于1的自然数。
- 由于3599的平方根为59.99…，所以只需要除以从2到59的数字。
- 费马测试被称为概率性素性测试，它判断的是“某个数是素数的概率大不大”。
- 实际上不只是5，对于任意素数p，上面的公式都是成立的。这就是“费马小定理”。根据是否满足费马小定理来判断一个数是否为素数的方法就是“费马测试”。
- 随机选择3个比113小的数作为n，计算这些数的113次方，再用113去除得到的结果，求出余数。3个数最后得到的余数都和原本的数相同，因此可以判断113是素数。
- 如果p是素数，那么所有比p小的数n都满足np mod p=n这个条件。但反过来，即使所有n都满足条件，p也有可能不是素数。因为在极低概率下会出现所有n都满足条件的合数（非素数的自然数）。
7-3 网页排名
- 网页排名（PageRank，也叫作佩奇排名）是一种在搜索网页时对搜索结果进行排序的算法。
- 网页排名就是利用网页之间的链接结构计算出网页价值的算法
- 在网页排名中，链入页面越多的网页，它的重要性也就越高。
- 如果一个网页链向多个页面，那么其链向的所有页面将平分它的权重。
- “随机游走模型”（random walk model）
- 用户浏览网页的操作就可以这样来定义：用户等概率跳转到当前网页所链向的一个网页的概率为1- α；等概率远程跳转到其他网页中的一个网页的概率为α。
- 以前的搜索引擎都是以关键词和网页内容的关联性来决定搜索结果的排列顺序，但这种方法没有考虑网页内是否含有有效内容，因此搜索精度较低。
7-4 汉诺塔
- 汉诺塔是一种移动圆盘的游戏，同时也是一个简单易懂的递归算法应用示例。
- 上面的公式即为T（n）=2n-1，这便是解决这个问题所需要的最短时间。