我的第一本算法书
2022-06-18 10:36:58 29 举报AI智能生成
登录查看完整内容
《我的第一本算法书》思维导图
作者其他创作
大纲/内容
加密
窃听
消息认证码/数字签名
假冒
篡改
数字签名
事后否认
数据传输时的四个问题
给需要保密的数据加密，加密后的数据称为\"密文\"
把密文恢复为原本数据的操作叫\"解密\"
对计算机来说，数据就是一串有意义的数字罗列(二进制串)，密文也是数字罗列，只不过它是计算机无法理解的无规律的数字罗列
加密就是用密钥对数据进行数值计算，把数据变成第三者无法理解的形式的过程
解密就是通过密钥进行数值计算，把密文恢复成原本数据的过程
加密的基础知识
哈希函数可以把给定的数据转换成固定长度的无规律数值，叫做\"哈希值\"
哈希值虽然是数字，但多用十六进制表示
输出的哈希值数据长度不变
输入的数据相同，输出的哈希值必定相同
即使输入的数据相似，哪怕只有一比特的差别，输出的哈希值也有很大的差异
哈希冲突：即使输入的两个数据完全不同，也有小概率出现输出的哈希值相同的可能性
不可逆性：无法根据哈希值反推原来的数据
哈希值的计算相对容易
MD5、SHA-1、SHA-2
若使用的哈希函数不同，那么就算输入的数据相同，得到的哈希值也是不同的
哈希函数的特征
哈希函数
共享密钥加密是加密和解密都使用相同密钥的加密方式
恺撒加密、AES、DES、动态口令
密钥交换协议
公开密钥加密
解决
共享密钥加密存在密钥被窃听的风险
共享密钥加密/对称加密
加密用的密钥叫作\"公开密钥\"P，解密用的密钥叫作\"私有密钥\"S
可以使用某个数值对数据进行加密
使用另一个数值对加密数据进行计算就可以让数据恢复原样
无法从一种密钥推算出另一种密钥
公开密钥加密算法的条件
RAS 算法、椭圆曲线加密算法
由接收方生成公开密钥和私有密钥，然后接收方把公开密钥发送给数据发送方，发送方用公开密钥进行加密，接收方用私有密钥解密
公开密钥和密文都是通过互联网传输的，因此可能会被 X 窃听。但是，使用公开密钥无法解密密文
公开密钥是不怕被人知道的，公开密钥可以被多个发送方获取；私有密钥不能被人知道，必须严密保管。
公开密钥加密加密和解密都比较耗时
font color=\"#ff0000\
公开密钥加密存在公开密钥可靠性的问题
公开密钥的可靠性会出现问题，就是因为 A 无法判断收到的公开密钥是否来自 B。用“数字证书”解决这个问题
公开密钥加密/非对称加密
混合加密中，用处理速度较快的共享密钥加密对数据进行加密，加密时使用的密钥需要用没有密钥分配问题的公开密钥加密进行处理。
假设A是发送方，B是接收方，A用共享密钥加密对数据加密，共享加密时的密钥设为A*，B事先生产公开密钥PB和私有密钥SB，B把PB发给A，A用PB对A*加密后把加密后的A*和密文发给B，B用SB解密A*，得到共享密钥，再用共享密钥解密密文
混合加密
持有P和P-S不能分解出S
P-S可以和P/S继续合成为P-S-P、P-S-S
密钥合成结果只和用了哪些密钥有关和合成顺序无关：A-B-C=A-C-B
即便 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个“簇”
什么是聚类
指定簇数和初始簇中心，重复执行“将数据分到相应的簇中”和“将中心点移到重心的位置”这两个操作，直到中心点不再发生变化为止
初始聚类中心不同，聚类结果不同
kmeans
聚类
欧几里得算法(辗转相除法)用于计算两个数的最大公约数GCD
先用大数作为被除数，小数作为除数，求出余数，然后余数和除数中小的数当作除数，大的数当作被除数，迭代计算，直到余数为0，此时的除数就是原始两个数字的最大公约数
欧几里得算法
素数就是只能被1和其本身整除，且大于1的自然数；素性测试就是判断一个自然数是不是素数
假如判断3599是不是素数：简单的方法便是将3599 按顺序除以比 2 大的数字，看是否能被整除，由于3599 的平方根为59.99…，所以只需要除以从2到59的数字，如果有能整除的，那么3599就不是素数；3599能被 59整除。也就是说，3599并不是素数。如果一个数非常大，这种方法会很慢
费马测试被称为概率性素性测试，它判断的是“某个数是素数的概率大不大”。
确认 n 和余数一致的次数越多，需要判断的数确实为素数的可能性就越大
如果p是素数，那么所有比p小的数n都满足n**p mod p ＝ n 这个条件。但反过来，即使所有n都满足条件， p也有可能不是素数，因为在极低概率下会出现所有n都满足条件的合数，这样的合数叫作\"卡迈克尔数\"，也叫\"绝对伪素数\"，这种数字非常少
AKS算法：在输入规模的多项式时间内进行（非概率意义，而是决定性的）素性测试，虽说是在多项式时间内但该算法的计算次数仍然较多，所以费马测试这样的高速算法更为实用
素性测试
网页排名（ PageRank，也叫作佩奇排名）是一种在搜索网页时对搜索结果进行排序的算法
网页排名就是利用网页之间的链接结构计算出网页价值的算法
网页排名
假设有n个圆盘，时间复杂度为
汉诺塔
其他算法
算法就是计算或解决问题的步骤
算法是严密的
程序是以计算机能够理解的编程语言编写而成，可以在计算机上运行算法是以人类能够理解的方式描述的，用于编写程序前
同一个算法，编程语言不同，写出来的程序不同；相同的编程语言，不同的人写出来的程序也不同
什么是算法
算法的时间复杂度是一个可以描述算法运行时间的函数，常用大O符号来表述，读作Order，大O表示法只取高阶项，忽略其他项
运行时间的计算方法
算法的基础知识
数据存储于内存时，决定了数据顺序和位置关系型的便是\"数据结构\"
根据使用目的选择合适的数据结构，可以提高内存的利用率
什么是数据结构
每个数据都有一个指针，指向下一个数据的内存地址
链表中的数据呈线性排列
因为数据分散储存，访问查找数据时只能从第一个数据开始顺序访问，时间复杂度O(n)
在链表中，数据一般是分散存储于内存中，无须存储在连续空间内
循环链表：一般链表尾部没有指针，若尾部使用指针并指向链表头部数据，将链表变成环形，即为循环链表
存储空间增加、添加\\删除数据时需要改变更多指针指向
双向链表：每个数据有两个指针，分别指向前后数据
链表
数组中数据呈线性排列
可以根据数据下标直接访问查找目标数据，即随机访问，O(1)
在数组中添加\\删除数据时，需要移动后面数据的位置，O(n)
数组中数据按顺序存储在内存的连续空间内
数组
栈中数据呈线性排列，只能访问最新添加的数据
往栈中添加数据的操作叫\"入栈push\"，从栈中取出数据的操作叫\"出栈pop\"
栈中最后添加的数据最先被取出，即\"后进先出\
在栈中，添加和删除数据的操作只能在一端进行，访问数据也只能访问到栈顶的数据。想要访问中间的数据，必须通过出栈操作将目标数据移到栈顶才行
括号匹配问题：(AB(C(DE)F))从左边读取字符，读到左括号将其入栈，读到右括号将栈顶的左括号出栈，出栈的左括号和当前的右括号匹配
深度优先搜索：通常选择最新的数据作为候补顶点，在候补顶点的管理上可以使用栈
在只需要访问最新数据时使用栈比较方便
栈
队列中数据呈线性排列
添加数据叫\"入队\"，删除数据叫\"出队\"
队列中最先进去的数据最先被取出，即\"先进先出\
广度优先搜索：通常选择最早的数据作为候补顶点，在候补顶点的管理上可以使用队列
队列
哈希表存储的是由键和值组成的数据，键是数据的标识符，值是数据的内容
开辟N个储存单元，通过哈希函数计算数据的键，即哈希值，将哈希值除以N取余数，即\"mod运算\"，将数据写入余数对应的储存单元中
利用链表在已有的数据后面插入新数据
链地址法
多次使用哈希函数或\"线性探测法\"寻找候补地址，直到有空地址
开放地址法
冲突
数组空间太大，内存浪费
可以利用哈希函数快速访问数组中的目标数据
哈希表
堆是一种图的树形结构，被用于实现\"优先队列\"，优先队列可以自由添加数据，但取出数据时要从最小值开始按顺序取出
在堆的树形结构中，各个顶点称为\"结点\"(node)，数据存储在结点中
1.堆中每个结点最多有两个子结点，结点的排列顺序为从上到下，同一行从左到右
2.堆中子结点必定大于等于父结点，因此最小值被存储在根结点——最小堆
3.往堆中添加数据时，一般把新数据放在最下面一行靠左的位置，最下面一行没有多余空间时，就另起一行，把数据放到新行的最左端
4.添加新元素后如果父节点大于子节点，不满足规则2，需要交换两个结点的位置，直到满足规则2.
5.从堆中取出数据时取出的是最上面的数据，取出后需要调整堆结构，使其满足规则2.，将最后的数据移到最顶端，如果子节点数据小于父节点，将父节点与其两个子节点的最小值交换，重复此操作直到数据都符合规则
6.堆中最顶端的数据始终最小，所以无论数据量有多少，取出最小值的时间复杂度都为 O(1)
7.取出数据后需要将最后的数据移到最顶端，然后一边比较它与子结点数据的大小，一边往下移动，重构时间O(logn)
9.如果需要频繁地从管理的数据中取出最小值，那么使用堆来操作会非常方便，如狄克斯特拉算法
堆的性质
堆
采用了图的树形结构，每个结点最多两个子节点
二叉查找树的最小值要从顶端开始往其左下的末端寻找
每个结点的值均大于其左子树上任意一个结点的值
二叉查找树的最大值要从顶端开始往其右下的末端寻找
每个结点的值均小于其右子树上任意一个结点的值
二叉查找树的性质
将要添加的数据先与顶端结点比较，小于它往左移，大于它往右移，不断比较不断移动，直到找到合适位置
添加数据
如果要删除的结点没有子结点，直接删掉该结点即可
如果要删除的结点只有一个子结点，先删掉目标结点，再将其子结点移到被删除结点的位置
如果需要删除的结点有两个子结点，先删除目标结点，再在被删除节点左子树中寻找最大节点(右子树中寻找最小节点)，最后将最大(最小)结点移到被删除结点的位置。如果需要移到的结点还有子节点，就递归前面的操作
删除数据
查找数据O(logn)：从二叉查找树的顶端结点开始往下查找。和添加数据时一样，把要查找的值和结点中的值进行比较，小于该结点的值则往左移，大于则往右移。
二叉查找树中一个结点最多有两个子结点，可以把子结点数扩展为m。像这种子结点数可以自由设定，并且形状均衡的树便是B树。
B树
二叉查找树\\二叉搜索树\\二叉排序树
数据结构
重复\"从序列右边开始比较相邻两个数字的大小，根据比较结果交换两个数字的位置\"这一操作
想象一个天平放在数组最右边两个数字上，比较它们并根据结果交换位置，将天平左移一位，继续比较，直到天平移到最左边两个数字，比较并交换后最左边数字即为最小值，此为\"一轮\"。接着将天平移到最右边两个数字，重复此操作，比较K轮后最左边K个数字已经排好序，无需再次比较
冒泡排序
重复\"从待排序数组中寻找最小值，将其与序列最左边的数字进行交换\"这一操作的算法，寻找最小值时采用线性查找
使用线性查找寻找最小值后与最左边数字交换，此为\"一轮\"；在余下数据中寻找最小值，将其与左边第二个数字交换，重复下去
选择排序
插入排序的思路就是从右侧未排序区域内取出一个数据，将它插入到左边已排序区域的合适位置
第一轮操作就是假设最左边的一个数字已经排好序，然后从待排序中取出最左边的数字，将它与左边已排好序的数字比较，根据比较结果交换位置，若取出的数字比左边已排序的数字都大，则不须交换
在插入排序中，需要将取出的数据与其左边的数字进行比较，如果左边的数字更小，就不需要继续比较，本轮操作到此结束。
如果取出的数字比左边已归位的数字都要小，就必须不停地比较大小，交换数字，直到它到达整个序列的最左边为止
在最糟糕的情况下，第 2 轮需要操作 1 次，第 3 轮操作 2 次……第 n 轮操作 n-1次，所以插入排序时间复杂度为O(n^2)
插入排序
堆排序一开始需要将 n 个数据存进堆里，所需时间为 O(nlogn)
每轮取出最大的数据并重构堆所需要的时间为 O(logn)，总共有 n 轮，所以重构后排序的时间也是 O(nlogn)，整体来看堆排序的时间复杂度为 O(nlogn)
最大堆
每轮取出最小的数据并重构堆所需要的时间为 O(logn)，总共有 n 轮，所以重构后排序的时间也是 O(nlogn)，整体来看堆排序的时间复杂度为 O(nlogn)
最小堆
利用堆进行排序
堆排序
归并排序算法会把序列分成长度相同的两个子序列，当无法继续往下分时（也就是每个子序列中只有一个数据时），就对子序列进行归并
归并指的是把两个排好序的子序列合并成一个有序序列。该操作会一直重复执行，直到所有子序列都归并为一个整体为止
将长度为 n 的序列对半分割直到只有一个数据为止时，可以分成 logn 行
每行都是n个数据，所以每行的运行时间都为 O(n)
归并排序的时间复杂度O(nlogn)
比较子序列中剩下的首位数字
归并排序
快速排序算法首先会在序列中随机选择一个基准值（ pivot），然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别
[ 比基准值小的数 ] 基准值 [ 比基准值大的数 ]
接着，对两个“[ ]” 中的数据进行排序之后，整体的排序便完成了。对“[ ]” 里面的数据进行排序时同样也会使用快速排序。
分治法+递归：递归结束条件：只有在[]里只剩一个数字的时候，排序才算完成
分割子序列时需要选择基准值，如果每次选择的基准值都能使得两个子序列的长度为原本的一半，那么快速排序时间复杂度为 O(nlogn)
固定基元：每次选择第一个或最后一个元素作为Pivot
随机基元
三数取中：使用左端、右端和中心位置上的三个元素的中值作为基准元
基准值选择
快速排序
排序
从头开始不断地按顺序检查数据，即便数据没有按顺序存储。线性查找的时间复杂度O(n)
线性查找
只能查找已经排好序的数据，二分查找的时间复杂度O(logn)
二分查找通过比较数组中间的数据与目标数据的大小，可以得知目标数据是在数组的左边还是右边。因此，比较一次就可以把查找范围缩小一半，查找范围内只剩一个数据时查找结束。
二分查找
数组的查找
由顶点和连接每对顶点的边所构成的图形就是图
给边加上一个值。这个值叫作边的“权重”或者“权”，加了权的图被称为加权图
有向图，加权有向图
什么是图
广度优先搜索优先从离起点近的顶点开始搜索
起点的子节点作为候补顶点，从候补顶点中选出一个顶点，优先选择最早成为候补的那个顶点，如果多个顶点同时成为候补顶点，那么可以随机选择一个作为顶点，由近及远进行广泛的搜索，直到找到目标顶点
广度优先搜索的候补顶点是用先入先出方式来管理的，因此可以使用“队列”进行管理
广度优先搜索
深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条候补路径
深度优先搜索优先选择最新成为候补的点，如果几个顶点同时成为候补，那么可以从中随意选择一个
深度优先搜索的候补顶点是用后入先出方式来管理的，因此可以使用“栈”进行管理
深度优先搜索
贝尔曼 - 福特（ Bellman-Ford）算法是一种在图中求解最短路径问题的算法
最短路径问题就是在加权图指定了起点和终点的前提下，寻找从起点到终点的路径中权重总和最小的那条路径
将图的顶点数设为 n、边数设为 m，贝尔曼-福特算法的时间复杂度为O(nm)
贝尔曼-福特算法可以用于无向图、有向图、边权为负的图
首先设置各个顶点的初始权重 ：起点为 0，其他顶点为无穷大；从所有的边中选出一条边，分别计算这条边从一端到另一端的权重，计算方法是“顶点原本的权重＋边的权重”；如果计算结果小于顶点的值，就更新这个值，更新时需要记录计算的是从哪个顶点到该顶点的路径；对所有的边都执行同样的操作更新完所有的边后，第1轮更新就结束了。接着，重复对所有边的更新操作，直到权重不能被更新为止
贝尔曼-福特算法
最短路径问题
首先设置各个顶点的初始权重： 起点为 0，其他顶点为无穷大；从起点出发，寻找可以从目前所在的顶点直达且尚未被搜索过的顶点，将它们设为下一步的候补顶点；计算各个候补顶点的权重。计算方法是“目前所在顶点的权重＋目前所在顶点到候补顶点的权重”，如果计算结果小于候补顶点的值，就更新这个值；从候补顶点中选出权重最小的顶点，将可以从新顶点直达的顶点设为新的候补顶点，用相同的方法计算各个候补顶点的权重，从候补顶点中选出权重最小的顶点；重复执行同样的操作直到到达终点
比起需要对所有的边都重复计算权重和更新权重的贝尔曼 - 福特算法，狄克斯特拉算法多了一步选择顶点的操作，这使得它求最短路径上更为高效。
将图的顶点数设为 n、边数设为 m，那么如果事先不进行任何处理，该狄克斯特拉算法的时间复杂度就是 O(n2)。如果对数据结构进行优化，那么时间复杂度就会变为O(m +nlogn)
如果图中含有负数权重，狄克斯特拉算法可能会无法得出正确答案
狄克斯特拉算法
狄克斯特拉算法会从离起点近的顶点开始，按顺序求出起点到各个顶点的最短路径。也就是说，一些离终点较远的顶点的最短路径也会被计算出来，但这部分其实是无用的；A* 就会预先估算一个值，并利用这个值来省去一些无用的计算
A*算法
图的搜索
我的第一本算法书
0 条评论
回复 删除
下一页
