总结

这篇文章作为对《我的第一本算法书》的总结，该书阐述了基本的算法和理念。
对于新手来说可以大致对算法及其应用有个概念，但是说不上可以让人真正学到算法
纯纯的入门书籍，本文将该书的重点进行了整理和归类

数据结构概述

[1.2 链表]
链表是利用指针作的数据结构，添加与删除都很简单
[1.3 数组]
数组与链表相反，通过下标来访问，导致其与链表相比访问简单而增删困难
[1.4 栈]
只能从最新的部分存读数据，通过Push加入，通过Pop取出
这种“先进后出”的结构被称为LIFO: Last In First Out
在使用递归的时候，就会接触到这种思想
[1.5 队列]
队列和栈相反，秉承着FIFO的原则，即First In First Out
最先进来的最先处理
——————————————————————————————|
[1.6 哈希表]
配合“哈希函数”进行数据的处理。核心是利用函数进行处理，再利用键值对来进行存读
存：利用哈希值与数组长度取余，得到该数据对应的位置。如果遇到冲突，则把后来的数据通过链表添加到前者之后
读：得到想要查询的数据的哈希值，然后进行mod(取余)运算，让我们知道它在哪个“箱子”中，然后通过链表线性查找

利用哈希表时，选择合适的数组长度很重要。

这种处理冲突的方法被称为“链地址法”，除此之外，运用广泛的还有：
开放地址法：发生冲突时立刻计算出一个候补地址，直到有空地址位置

[1.7 堆]
堆是一种图的树形结果，被用于实现“优先队列”。
（优先队列是一种数据结构，可以自由添加数据，但取出数据的时候要从最小值开始按顺序取出）
在堆的树形结构中，各个顶点被称为“结点”，数据就存储在结点中
（结点按照从上到下，从左到右的顺序排列）
堆的一个原则是：子结点必须大于父结点
堆时候在需要频繁地从管理的数据中取出最小值的情况

[1.8 二叉查找树]
1.每个结点最多有两个子结点
2.每个结点的值均大于其左子树上的，任意一个结点的值
3.每个结点的值均小于其右子树上的，任意一个结点的值
4.查找最小结点从顶端开始，往左下的末端寻找。最大结点则反之，从顶端向右下末端寻找
5.添加数据时，通过不断比较大小选择左右方向，往下进行
6.可以把二叉查找树当成二分算法的树形结构体系

排序概述

冒泡排序
从右向左开始比较，根据结果排序。让最大的数字置于左边
对于冒泡排序，总的比较次数一直为n²/2,与数值最开始排列方式无关

选择排序
与线性搜索配合的算法，“从待排序的数据中寻找最小值，如何与序列最左边的数字进行交换”
每一次操作的实质都是寻找到最小值，然后扔到前面去。在前面自然而然，会按最小值排好
次数同样是n²/2

插入排序
“从左向右”的排序方法，本质是从右侧的“未排序区域”取出一个数据，然后插到左边的“已排序区域”中去
如果要细究的话还是比较吃运气的，如果每次拿到的数字都比左边已归为数字要小，那么效率就会大大降低
（当然，数据不多的话这种“降低”和“运气成分”可以忽略不计）

堆排序
利用了数据结构的“堆”进行的排序（“堆”的概述可以看前面）
在这里，我们以降序来构建堆（之前提到的堆是“子结点一定大于父结点”的升序）
我们从降序排列的堆中取出数据，就会从最大的数据开始去，将取出的数据反序输出，排序就完成了

归并排序
归并：把两个排好序的子序列合并成一个有序的序列
归并排序会把序列分成长度相等的两个子序列，当无法继续下分（每个序列都只有一个数据了），进行归并
归并两个子序列时，比较它们的首位数字，并且移动较小的数字到合并序列的首位
不断进行上面的步骤，直到所有数字合并为一个序列整体
归并排序的运行时间与堆序列相同

快速排序
快速排序的步骤如下
1.在序列中随机选择一个值作为“基准值pivot”
2.把其它数值分为“比基准值小”和“比基准值大”两个部分
3.然后依据2，我们可以得到这样一个排序： [比基准值小] 基准值 [比基准值大]
4.然后在对前后的[]中的数据再次进行快速排序，直到完成

查找与搜索

查找

线性查找
可以说是最简单的查找方法了，从头开始往下一直找，直到找到或者到尾为止

二分查找
聪明一点的查找方法
适用于已经排序好的数组，二分查找每次都会把查找范围通过大小比较来缩短一半

搜索

图
这里是说的是计算机科学/离散数学中说的图。各圈被称为“顶点”，连接顶点的线叫做“边”
我们还可以为边加上一个值，这被称为“权重/权”，加了权的图就是“加权图”。没有权的边只表示两个顶点的连接状态，有权的则可以表示连接程度
我们也可以为边加上一个箭头，这样的图被称为“有向图”

图的搜索指的就是“从图的某一项顶点开始时，通过边达到不同的顶点，最终找到目标顶点”的过程
根据搜索顺序的不同，我们可以将搜索顺序分为 “广度优先” 和 “深度优先”

没有闭环的图被称为“树”

广度优先搜索
广度优先搜索的特征是，从起点开始由近及远进行广泛的搜索
1.从起点开始，顺着边进行搜索，直到达到指定顶点（终点/目标点）
2.没到一个顶点，就进行一次“是否为终点”的判断
3.优先从离起点进的顶点开始搜索

深度优先搜索
深度优先与广度优先的区别在于，它会沿着一条路径不断往下搜索，直到不能继续搜索为止，然后再折返
二者在操作步骤上仅有一个地方不同：选择哪一个候补顶点作为下一个顶点的基准不同

算法

贝尔曼-福特算法
这是一种在图中求解最短路径的算法。
这里指在加权图指定了起点和终点的前提下，寻找从起点到终点的路径中“权重总和”最小的那条，做法如下：
1.先设置各个点的权重：先把起点设置为0，其余设置为无穷大。此时我们能得到的就是最短路径的暂定路径，随着计算往下，这个值会收敛变小
2.从连接起点的所有边中选择一条边，计算这条边从一端到另外一端的权重。计算方式是“原本的权重+边的权重”（按顺序计算）
3.更新：如果在2的计算结果小于顶点原本的值，那么就更新这个值。更新时需要记录是从哪个顶点到该路径的顶点
比如，A-B,A为0，B为无穷大，二者间的边的值为9.那么这次得到的权重是0+9=9，9<无穷大，则将B的权重改为9
4.同样计算B到A的权重，此时数值为9(B)+9(边) = 18 ，显然这个权重比A的0大，所以不更新。
我们可以任务，从权重大的点到小的点时，只要边的权重不为负数，那么就不会更新
5.对所有边执行2—4的操作。
6.当对所有路径都进行了5之后，则代表我们进行了第一轮的更新。接着我们再次重复对所有边进行更新操作，直到权重不能更新为止。

附：设图的顶点数为n，若对于一个“边的权重总和是负数的闭环”，不存在最短路径。在对于进行了n次更新，仍然还有可更新顶点的情况，则可以直接认定其不存在最短路径。

狄克斯特拉算法
另外一种求解最短路径的方法
狄克斯特拉算法与贝尔曼-福特算法的不同在于，其一边逐一确定起点到各个顶点的最短路径，一边对图进行搜索（而贝尔曼-福特算法则是在一次次权重刷新中确定最短路径）
比起需要对所有的边都进行重复计算/更新权重的贝尔曼-福特算法，狄克斯特拉算法多了一步选择顶点的操作，因此在求解上更加高效

但是，如果图中含有负数的权重，那么该算法可能无法得出正确答案
（在贝尔曼-福特算法中，可以直接认定不存在，在狄克斯特拉算法则会给出一个错误的答案）

总结：不存在负数权重时，更适合使用效率较高的“狄克斯特拉算法”，而存在负数权重时则使用“贝尔曼-福特算法”（即使较为耗时）

A*算法/A星算法
由狄克斯特拉算法发展而来的算法，A会预估一个值进行计算（这个计算可能是无用的）
狄克斯特拉算法只能根据起点到候补顶点的距离来决定下一个顶点。
而A算法不仅会考虑从起点到候补顶点的距离，还会考虑从当前点到终点的“估算距离”。其算法如下：
1.计算起点和周围每个顶点的权重，计算方法是“起点到顶点的距离” + “距离估算值”
2.选择一个权重最小的顶点，并把它设置为搜索完毕的状态
3.计算“搜索完毕的顶点”到下一个顶点的权重，并再次得到一个搜索完毕的顶点
4.重复2-3直到到达终点

A*算法中，当距离估算值约接近于实际值时，其搜索效率就会越高。若二者差距过大，则会导致效率降低（甚至不如狄克斯特拉），还有可能导致无法得到正确的答案

安全算法

互联网传输数据时可能遇到四个经典的问题“窃听”，“假冒”，“篡改”，“事后否认”
这四个问题不仅仅可能发生在用户交流时，也可能发生在用户浏览网页时
为了解决这四个问题，我们有下列四个方法来应对问题，分别是“加密”，“消息认证码”，“数字签名”。

“窃听”————“加密”
“假冒” “篡改” —“消息认证码”，“数字签名”
“事后否认”——–“数字签名”

“加密”的基础知识

计算机中的各个数据本质就是0和1，加密就表示：数据经过某种运算之后，变成一个计算机无法理解的数。此时我们会用到“密钥”
加密就是用密钥对数据进行数值运算而变成第三者无法理解的形式的过程
解密就是用密钥进行数值计算而把密文恢复成原本数据的过程

哈希函数
哈希函数可以把给定的数据转换成固定长度的无规律数值。这个“无规律数值”就被称为“哈希值”，其具有以下特征：
1.无论数据原本的大小如何，输出的哈希值数据长度不变
2.如果输入的数据相同，那么输出的数据也必定相同
3.即使输入的数据再相似，它们输出的哈希值也会有很大差异。输入相似的数据并不代表得到的哈希值也相似
4.“哈希冲突”:即使输入的两个数据完全不同，输出的哈希值也有可能是相同的，这种情况的概率很低
5.不可能从哈希值反向推算出原本的数据
6.求哈希值的计算相对容易

共享密钥加密
加密的方式分为两种
1.加密和解密都使用相同密钥的“共享密钥加密”
2.分别使用不同密钥的“公开密钥加密”

“共享密钥加密”是加密和解密都使用相同密钥的加密方式，也被称为“对称加密”
实现共享密钥加密的算法有“凯撒密码”，AES,DES，动态口令等，其中AES应用最广

公开密钥加密
加密和解密使用不同密钥的加密方式。加密用的密钥叫“公开密钥”，解密用的密钥是“私有密钥”
这种加密方式也被叫做“非对称加密”
实现公开密钥加密的方法有：RAS算法，椭圆曲线算法等。应用最广的RSA算法
这种算法必须满足以下条件：
1.可以使用某个数值对数值进行加密
2.使用另一个数值对加密数据进行计算就可以让数据恢复原样
3.无法从一种密钥推算出另外一种密钥

公开密钥可能遭受“中间人攻击”：一种通过中途替换公开密钥来窃听数据的攻击方法。

混合加密运算
混合加密运算就是上述两种加密方式的互补
主要原理：用处理速度较快的共享密钥加密对数据加密（加密使用没有密钥分配问题的公开密钥加密处理）

步骤如下（假设在AB之间传输数据）
1.A先用处理速度较快的共享密钥加密对数据进行处理。因此B也需要对应的密钥来解密（A要把密钥给B）
2.将上述所需要的密钥进行公开密钥加密处理，发送该密钥（B需要事先持有对应的公开密钥和私有密钥）
3.B将公开密钥发送给A，A使用该密钥来加密“共享密钥加密中所需要的那个密钥”
4.A将加密完成之后的“共享密钥加密中所需要的那个密钥”发送给B
5.B用2提到的“事先持有的私有密钥”进行解密。此时A已经成功把共享密钥加密中使用的密钥安全发送给B了
6.准备工作完成，A现在只要把使用该共享密钥加密好的数据发送给B即可。

总结：
混合加密在安全性和处理速度上都具有有势，为网络通讯提供通信安全的SSL协议就应用了混合加密的方法

在升级之后，SSL现已被正式命名为TLS协议。

迪菲-赫尔曼密钥交换

迪菲-赫尔曼密钥交换是一种可以在通信双方之间安全交换密钥的办法。
这种方法通过将双方共有的秘密数值隐藏在公开数值相关的运算中，来实现双方之间密钥的安全交换。
我们假设有一种方法可以合成两个密钥，可以用它合成来密钥P和密钥S。就会得到由这两个密钥的成分所构成的密钥P-S
这种合成方法应该有一下三种特征：
1.即使持有密钥P和合成密钥P-S，也无法把S单独提取出来
2.不该之前合成的密钥如何，都可以把它作为新元素来继续与其它密钥合并
3.密钥合成的结果只与用了哪些密钥有关，与合成顺序无关

迪菲-赫尔曼密钥交换，通信双方仅通过交换一些公开信息就可以实现密钥交换，而实际上并非“交换”密钥，而是双方生成了密钥

消息认证码

消息认证码可以实现“认证”和“检测篡改”两个功能，简略的实现如下
1.A向B发送消息时，同时生成了一个用于制作消息认证码的密钥，同样用安全方法发给了B
2.A用密文和上述的密钥生成了一个值，这个值就是消息认证码，简称MAC。我们可以把MAC想象成是用密钥和密文组成的字符串的“哈希值”
3.接下来，B只需要解密即可。当计算MAC时，若发现和自己收到的MAC不同，则可以发现消息的篡改

数字签名
数字签名不仅可以实现认证和检测篡改的功能，还可以预防“事后否认”的出现，因为数字签名是只有发信人才可以生成的
数字签名的生成使用用的是公开密钥加密。发送者将公开密钥发给收信人，而自己使用私有密钥加密，这样就得到了数字签名（这和一般的公开密钥加密是相反的）

数字证书
在“公开密钥加密”配合“数字签名”时，无法保证公开密钥确实来自消息的发送者，而数字证书就能保持公开密钥的正确性。
数字证书主要需要利用的认证中心，与“算法概念”已经没有很大关系了，因此不赘述

聚类概述以及其它

聚类就是“在输入为多个数据时，将相近的数据分为一组”的操作。一个组就叫作一个“簇”
那么，怎么判断“相近”呢？
实际上，根据数据类型的不同，定义该数据是否“相近”的标准也不同。具体来说就是要对两个数据的“差距”进行定义

k-means算法

聚类算法中的一组，可以根据事先给定的簇的数量进行聚类
假设数据位于平面上：
1.随机选择N个点作为簇的中心点
2.计算各个数据分别和三个中心点中的哪一个点距离最近，将数据分到相应的簇中
3.计算各个簇中数据的中心，将各个簇的中心点移动到这个位置
4.重新计算“距离簇中心点最近的数据”，再次将数据分到对应簇中
5.重复执行3-4的操作直到中心点不再变化