前言

昨天晃了晃《我的第一本算法书》这本书，对算法有了大致的了解，当然，有些比较难的没有理解到，也没有实操，这里简单记录一下吧。

导论

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

解决问题的算法不止一种，需要根据实际情况选择合适的算法。

求运行时间

不同的算法的运行时间是不同的，计算算法的运行时间时，使用步数来衡量一个算法的时间，一步就是计算的基本单位。

将程序中最基本的运算记为一个步数，如变量的赋值。

运行时间的计算公式如下所示，括号内的内容表示总步数，使用$O()$括上后表示忽略重要项以外的内容读音同Order，含义为运行时间最长也就是n^2的常数倍。
$$
O(7n^2 + 2n + 4) = O(n^2)
$$

数据结构

大部分的算法都是基于数据结构来实现的，需要了解常用的数据结构，数据结构即决定了数据的顺序和位置关系。

  1. 链表：线性排列，数据添加、删除方便，访问耗时。

  2. 数组：线性排列，访问数据简单，插入、删除数据耗时。

  3. 栈：线性排列，只能访问最新添加的数据。

  4. 队列：线性排列，先进先出。

  5. 哈希表：key-value值的链表数组，获取key的哈希值，放到对应下标的链表中（哈希冲突往链表追加）

    1. 链地址法：哈希冲突后，在链表后追加
    2. 开放地址法：哈希冲突后，重新计算候补地址，直到有空地址位置。

  6. 堆：一种图的树形结构，使用较少

    每个节点最多有两个子节点，节点顺序从上到下，从左到右

    子节点必须大于父节点

排序

  1. 选择排序：重复从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换。
  2. 插入排序：从序列左端开始依次对数据进行排序。
  3. 堆排序：利用堆的特性，一直取最顶端的数据（最小值）即可，每次取完需要重新刷新堆结构。
  4. 归并排序：递归，把序列分成长度相同的两个子序列进行排序，当无法下分时（子序列只有一个数据）归并为一个整体。
  5. 快速排序：从序列中随机选一个基准值，分为比基准值大的序列和比基准值小的序列，对这两个序列执行相同的操作，直至排序完成。

查找

  1. 线性查找：一个一个挨个找。
  2. 二分查找：只能从排好序的序列中查找，一半一半地找。

图

顶点和边组成的结构。

  1. 加权图：边有值，这个值为边的“权重”或“权”，表示顶点之间的连接程度。
  2. 有向图：边有方向，顶点之间可能不互达。

查找

  1. 广度优先：按树结构一层一层地查找。
  2. 深度优先：按树结构一个枝条一个枝条地查找，枝条到底后再返回查找其他枝条。
  3. 贝尔曼-福特算法：待理解
  4. 狄克斯特拉算法：待理解
  5. A*算法：待理解

安全算法

为了解决数据在网络传输中发生的各种安全问题，窃听、假冒、篡改、事后否认。

  1. 哈希函数：一种将数据转换为加密的固定长度的字符串（如：MD5加密），具有以下特征：
    1. 输出的哈希值数据长度不变
    2. 输入的数据相同，输出的哈希值相同
    3. 输入的数据相似，输出的哈希值也会有很大的差异
    4. 输入的两个数据完全不同，输出的哈希值可能相同（哈希冲突）
    5. 不能从哈希值反推出输入的数据
  2. 共享密钥加密：加密、解密都使用相同密钥，会有密钥被监听的风险
  3. 公开密钥加密（非对称加密）：加密、解密使用不同的密钥，密钥和加密后的数据有被篡改的风险
    1. 加密用的密钥叫做公开密钥，解密用的密钥叫做私有密钥
    2. 接受方生成空开密钥和私有密钥，将公开密钥交给发送方加密数据，使用私有密钥才能解密
  4. 混合加密：共享密钥加密存在密钥的安全问题，公开密钥加密存在加密解密速度慢的问题，使用公开密钥加密 加密 共享密钥加密 的密钥，数据使用共享密钥机密密钥进行加密。
    1. 接收方生成公开密钥与私有密钥，将公开密钥交给发送方，发送方使用公开密钥加密共享密钥后发送给接收方
    2. 发送方使用共享密钥加密数据，发送给接收方
    3. 接收方收到被加密的共享密钥与被加密的数据，使用私有密钥解密共享密钥，使用共享密钥解密被加密的数据
  5. 迪菲赫尔曼密钥交换：密钥与密钥之间的合成，密钥只能合成，合成的结果与合成顺序无关，不同顺序合成的结果也相同，不能拆解，双方交换密钥是安全的。
    1. 一方A与一方B需要交换密钥SA与SB
    2. 一方A生成一个可泄露的密钥P，将密钥P发送给另一方B
    3. A将密钥P与密钥SA合成为密钥P-SA，B将密钥P与密钥SB合成P-SB
    4. A将密钥P-SA交给B，B将密钥P-SB交给A
    5. A将密钥P-SB与密钥SA合成为密钥P-SB-SA，B将密钥P-SA与密钥SB合成为密钥P-SA-SB
    6. A和B共同获得了一个相同的安全的密钥P-SA-SB（与P-SB-SA相同，与顺序无关）
  6. 消息认证码：为了防篡改，在数据末尾加上认证码，根据解密后的数据运算后得到的数据与认证码不相等则消息被篡改。
  7. 数字签名：防止事后否认，待理解。
  8. 数字证书：待理解

聚类

根据规则将离散的数据归类。

k-means算法：不太理解。

其他

  1. 欧几里得算法（辗转相除法）：用于求两个数的最大公约数，用小的数除大的数得到余数，再用余数去除除数（第一次为小的数）得到新的余数，重复操作，知道余数为零时，此时的除数即为最大公约数。

  2. 素性测试：判断一个自然数是否为素数。

    可以用费马测试：概率性素性测试，用于判断某个数是素数的概率大不大，并不能做到百分百确定。

    随机选择三个比待判断数P小的数num1、num2、num3，这三个数的P次方 除以 P 得到的商r1、r2、r3分别等于num1、num2、num3，则基本可以确定此数为素数。

    $num1^P \div P = num1$
    $num2^P \div P = num2$
    $num3^P \div P = num3$

  3. 汉诺塔：需要在三根柱子中移动圆盘，开始时，圆盘按从小到大的顺序叠放在第一根柱子上，需要将圆盘转移到第三根柱子上，并且转移过程中，大的圆盘不能叠放在小的圆盘上面。

最后

感觉需要学习的地方还有好多好多，怎么入个门都这么吃力，慢慢来吧！