算法

五大常用算法

分治算法

基本概念：把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
运用：排序算法（快速排序，归并排序）、傅立叶变换（快速傅立叶变换）、二分搜索、大整数乘法、Strassen 矩阵乘法、棋盘覆盖、线性时间选择、最接近点对问题、循环赛日程表、汉诺塔……
分治法所能解决的问题一般具有以下几个特征：

该问题的规模缩小到一定的程度就可以容易地解决

该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

利用该问题分解出的子问题的解可以合并为该问题的解；

该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

说明：第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；
第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；
第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。
第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

分治法在每一层递归上都有三个步骤：

分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题

合并：将各个子问题的解合并为原问题的解。

动态归纳

基本概念：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。
与分治法之间的区别：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。
能采用动态规划求解的问题的一般要具有 3 个性质：

最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

动态规划的设计都有着一定的模式，一般要经历以下几个步骤：

划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。

确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。

确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。

寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

贪心算法

基本概念：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
运用：Prim算法、Kruskal算法（都是求最小生成树的）
基本思路：将问题分解为若干个小问题，逐渐求得各个子问题的局部最优解，最后合并为原来问题的解
贪婪算法可解决的问题通常大部分都有如下的特性：

随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。

有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。

还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。

选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。

最后，目标函数给出解的值。

为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数，贪婪算法一步一步的进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最优的。

贪心算法的实现框架

从问题的某一初始解出发；
while （能朝给定总目标前进一步）
{
利用可行的决策，求出可行解的一个解元素；
}
由所有解元素组合成问题的一个可行解；

回溯算法

基本概念：回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

分支限界

基本概念：类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。
与回溯算法的区别：分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

加密算法

加密和解密
- 加密
  - 数据加密的基本过程，就是对原来为明文的文件或数据按某种算法进行处理，使其成为不可读的一段代码，通常称为“密文”。通过这样的途径，来达到保护数据不被非法人窃取、阅读的目的。
- 解密
  - 加密的逆过程为解密，即将该编码信息转化为其原来数据的过程。
加密方式
- 对称加密算法
  - 的加密与解密密钥相同，又称为共享密钥加密算法。
  - 流程
    - 数据加密过程：在对称加密算法中，数据发送方将明文（原始数据）和加密密钥一起经过特殊加密处理，生成复杂的加密密文进行发送。
    - 数据解密过程：数据接收方收到密文后，若想读取原数据，则需要使用加密使用的密钥及相同算法的逆算法对加密的密文进行解密，才能使其恢复成可读明文。
  - 常见算法
    - DES 算法
      - DES 加密算法是一种分组密码，以 64 位为分组对数据加密，它的密钥长度是 56 位，加密解密用同一算法。
      - DES 加密算法是对密钥进行保密，而公开算法，包括加密和解密算法。这样，只有掌握了和发送方相同密钥的人才能解读由 DES 加密算法加密的密文数据。因此，破译 DES 加密算法实际上就是搜索密钥的编码。对于 56 位长度的密钥来说，如果用穷举法来进行搜索的话，其运算次数为 $2^56$ 次。
    - 3DES 算法
      - 是基于 DES 的对称算法，对一块数据用三个不同的密钥进行三次加密，强度更高。
    - AES 算法
      - AES 加密算法是密码学中的高级加密标准，该加密算法采用对称分组密码体制，密钥长度的最少支持为 128 位、 192 位、256 位，分组长度 128 位，算法应易于各种硬件和软件实现。这种加密算法是美国联邦政府采用的区块加密标准。
      - AES 本身就是为了取代 DES 的，AES 具有更好的安全性、效率和灵活性。
- 非对称加密算法
  - 的加密密钥与解密密钥不同，又称为公开密钥加密算法。
  - 需要两个密钥，一个称为公开密钥（public key），即公钥，另一个称为私有密钥（private key），即私钥。
  - 流程
    - 如果使用公钥对数据进行加密，只有用对应的私钥才能进行解密。
    - 如果使用私钥对数据进行加密，只有用对应的公钥才能进行解密。
  - 常见算法
    - RSA 算法
      - RSA 加密算法是目前最有影响力的公钥加密算法，并且被普遍认为是目前最优秀的公钥方案之一。RSA 是第一个能同时用于加密和数字签名的算法，它能够抵抗到目前为止已知的所有密码攻击，已被 ISO 推荐为公钥数据加密标准。
      - RSA 加密算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。
      - 原理
        
        例子
        
        假如原文是 123
        
        $123*13=1599$，我取后 3 位即 599 作为密文，然后取 13 作为加密密钥，关键来了，如果要对 599 进行解密，按照以往的思路，是不是要做除法？但是你的密文是 599，你并不知道 1599 这个完整的信息，所以不能直接做除法，那怎么办呢？
        
        $599*77=46123$，然后我取 46123 的后 3 位，其中 77 是解密密钥
        
        那么上面的这个加密和解密用的都是乘法，加密解密不是互逆的运算，这就是非对称。
        
        那么这个 13 和 77 为什么是这两个数字呢？其实 $13*77=1001$，任何三位正整数 abc 乘以 1001 结果都是 abcabc, 所以才能保证原文的正确还原
    - ECC 算法
      - ECC 也是一种非对称加密算法，主要优势是在某些情况下，它比其他的方法使用更小的密钥，比如 RSA 加密算法，提供相当的或更高等级的安全级别。不过一个缺点是加密和解密操作的实现比其他机制时间长（相比 RSA 算法，该算法对 CPU 消耗严重）。
- 不需要密钥的散列算法
  - 常见算法
    - MD5 算法
      - MD5 用的是哈希函数，它的典型应用是对一段信息产生信息摘要，以防止被篡改。严格来说，MD5 不是一种加密算法而是摘要算法。无论是多长的输入，MD5 都会输出长度为 128bits 的一个串（通常用 16 进制表示为 32 个字符）。
    - SHA1 算法
      - SHA1 是和 MD5 一样流行的消息摘要算法，然而 SHA1 比 MD5 的安全性更强。对于长度小于 $2^64$ 位的消息，SHA1 会产生一个 160 位的消息摘要。基于 MD5、SHA1 的信息摘要特性以及不可逆（一般而言），可以被应用在检查文件完整性以及数字签名等场景。
    - HMAC 算法
      - HMAC 是密钥相关的哈希运算消息认证码（Hash-based Message Authentication Code），HMAC 运算利用哈希算法（MD5、SHA1 等），以一个密钥和一个消息为输入，生成一个消息摘要作为输出。
      - HMAC 发送方和接收方都有的 key 进行计算，而没有这把 key 的第三方，则是无法计算出正确的散列值的，这样就可以防止数据被篡改。
- 混合加密
  - 由于以上加密算法都有各自的缺点（RSA 加密速度慢、AES 密钥存储问题、MD5 加密不可逆），因此实际应用时常将几种加密算法混合使用。
  - 常见算法
    - RSA + AES
      - 采用 RSA 加密 AES 的密钥，采用 AES 对数据进行加密，这样集成了两种加密算法的优点，既保证了数据加密的速度，又实现了安全方便的密钥管理。
- 其他
  - Base64
    - Base64 编码之所以称为 Base64，是因为其使用 64 个字符来对任意数据进行编码，同理有 Base32、Base16 编码。
    - 标准 Base64 编码使用的 64 个字符为：
      - 这 64 个字符是各种字符编码（比如 ASCII 编码）所使用字符的子集，基本，并且可打印。唯一有点特殊的是最后两个字符，因对最后两个字符的选择不同，Base64 编码又有很多变种，比如 Base64 URL 编码。
    - 原理
      - Base64 编码本质上是一种将二进制数据转成文本数据的方案。对于非二进制数据，是先将其转换成二进制形式，然后每连续 6 比特（$2^6=64$）计算其十进制值，根据该值在上面的索引表中找到对应的字符，最终得到一个文本字符串。
    - Base64 编码是每 3 个原始字符编码成 4 个字符，如果原始字符串长度不能被 3 整除，那怎么办？使用 0 值来补充原始字符串。
      - 最后 2 个零值只是为了 Base64 编码而补充的，在原始字符中并没有对应的字符，那么 Base64 编码结果中的最后两个字符 AA 实际不带有效信息，所以需要特殊处理，以免解码错误。
      - 标准 Base64 编码通常用 = 字符来替换最后的 A，即编码结果为 SGVsbG8hIQ==。因为 = 字符并不在 Base64 编码索引表中，其意义在于结束符号，在 Base64 解码时遇到 = 时即可知道一个 Base64 编码字符串结束。
      - 解码是对编码的逆向操作，但注意一点：对于最后的两个 = 字符，转换成两个 A 字符，再转成对应的两个 6 比特二进制0值，接着转成原始字符之前，需要将最后的两个 6 比特二进制 0 值丢弃，因为它们实际上不携带有效信息。

排序算法

分类
- 根据排序的空间来分
  - In-place sort（内部排序）
    - 在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序
    - 当需要对大量数据进行排序时，In-place sort 就显示出优点，因为只需要占用常数的内存
    - 排序方式
      - 插入排序、选择排序、冒泡排序、堆排序、快速排序
  - Out-place sort（外部排序）
    - 在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序
    - 排序方式
      - 归并排序、计数排序、基数排序、桶排序
- 根据排序的稳定性来分
  - stable sort（稳定排序）
    - 有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就说这种排序方法是稳定的
    - 排序方式
      - 插入排序、冒泡排序、归并排序、计数排序、基数排序、桶排序
  - unstable sort（非稳定排序）
  - 排序方式
    - 选择排序、快速排序、堆排序
排序算法
- 插入排序
  - 基本思路：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
  - 时间复杂度：
    - 最优复杂度：当输入数组就是排好序的时候，复杂度为 $O(n)$，而快速排序在这种情况下会产生 $O(n^2)$ 的复杂度。
    - 最差复杂度：当输入数组为倒序时，复杂度为 $O(n^2)$。
  - 插入排序包括：
    - 直接插入排序
      - 基本思路：把待排序的纪录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的纪录插入完为止，得到一个新的有序序列
      - 稳定性：稳定排序
    - 二分插入排序（又称折半插入排序）
      - 将直接插入排序中寻找 A[i] 的插入位置的方法改为采用折半比较，即可得到折半插入排序算法。
      - 稳定性：稳定排序
      - 算法过程
        
        计算 0 ~ i-1 的中间点，用 i 索引处的元素与中间值进行比较，如果 i 索引处的元素大，说明要插入的这个元素应该在中间值和刚加入i索引之间，反之，就是在刚开始的位置到中间值的位置，这样很简单的完成了折半；
        
        在相应的半个范围里面找插入的位置时，不断的用（1）步骤缩小范围，不停的折半，范围依次缩小为 1/2 1/4 1/8 …….快速的确定出第 i 个元素要插在什么地方；
        
        确定位置之后，将整个序列后移，并将元素插入到相应位置。
    - 链表插入排序
- 希尔排序（又称缩小增量排序）。
  - 希尔排序法又称缩小增量法。是插入排序的一种变种。
  - 稳定性：不稳定
  - 基本思路：把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
  - 时间复杂度：希尔排序的时间复杂度与增量序列的选取有关。例如希尔增量时间复杂度为 $O(n^2)$，而 Hibbard 增量的希尔排序的时间复杂度为 $O(n^{\frac{3}{2}})$，希尔排序时间复杂度的下界是 $O(n*log2n)$。
  - 希尔排序没有快速排序算法快 $O(n(logn))$，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。
  - 本质上讲，希尔排序算法是直接插入排序算法的一种改进，减少了其复制的次数，速度要快很多。原因是，当n值很大时数据项每一趟排序需要的个数很少，但数据项的距离很长。当n值减小时每一趟需要和动的数据增多，此时已经接近于它们排序后的最终位置。正是这两种情况的结合才使希尔排序效率比插入排序高很多。
- 冒泡排序
  - 基于交换排序的一种算法。
  - 稳定性：稳定
  - 时间复杂度：
    - 最坏运行时间：$O(n^2)$；
    - 最佳运行时间：$O(n^2)$（当然，也可以进行改进使得最佳运行时间为 $O(n)$）
  - 基本思路：通过两两交换，像水中的泡泡一样，小的先冒出来，大的后冒出来。
- 选择排序
  - 稳定性：不稳定
  - 时间复杂度：
    - 最好情况时间：$O(n^2)$。
    - 最坏情况时间：$O(n^2)$。
  - 基本思路：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
- 归并排序
  - 时间复杂度：
    - 最坏情况运行时间：$O(nlogn)$。
    - 最佳运行时间：$O(nlogn)$。
  - 速度仅次于快速排序
  - 稳定性：稳定
  - 基本思路：运用分治法思想解决排序问题
  - 算法过程
    1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
    2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
    3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
    4. 重复步骤 3 直到某一指针超出序列尾
    5. 将另一序列剩下的所有元素直接复制到合并序列尾
- 快速排序
  - 被誉为“20世纪十大经典算法之一”。
  - 时间复杂度：
    - 最坏运行时间：当输入数组已排序时，时间为 $O(n^2)$，当然可以通过随机化来改进（shuffle array 或者 randomized select pivot），使得期望运行时间为 $O(nlogn)$。
    - 最佳运行时间：$O(nlogn)$。
  - 稳定性：不稳定
  - 基本思路：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
- 堆排序
  - 时间复杂度：
    - 最优时间：$O(nlogn)$。
    - 最差时间：$O(nlogn)$。
  - 稳定性：不稳定
  - 基本思路：堆排序利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，使得在当前无序区中选取最大（或最小）关键字的记录变得简单。
  - 堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。
  - 大根堆和小根堆：根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小者的堆称为小根堆，又称最小堆。根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆。
- 计数排序
  - 是一个非基于比较的排序算法
  - 时间复杂度：
    - 最坏情况运行时间：$O(n+k)$。
    - 最好情况运行时间：$O(n+k)$。当 $k=O(n)$ 时，计数排序时间为 $O(n)$
  - 稳定性：稳定
  - 基本思路：对于给定的输入序列中的每一个元素 x，确定该序列中值小于 x 的元素的个数。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。
  - 它的优势在于在对一定范围内的整数排序时，它的复杂度为 $Ο(n+k)$（其中k是整数的范围），快于任何比较排序算法。
- 基数排序
  - 时间复杂度：
    - 最坏情况运行时间：$O((n+k)d)$。
    - 最好情况运行时间：$O((n+k)d)$。
  - 稳定性：稳定
  - 基本思路：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
- 桶排序
  - 时间复杂度：
    - 最坏情况运行时间：当分布不均匀时，全部元素都分到一个桶中，则 $O(n^2)$，当然也可以将插入排序换成堆排序、快速排序等，这样最坏情况就是 $O(nlgn)$。
    - 最好情况运行时间：$O(n)$
  - 稳定性：稳定
  - 基本思路：工作的原理是将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。
  - 桶排序是鸽巢排序的一种归纳结果。
  - 桶排序非常快，但是同时也非常耗空间，基本上是最耗空间的一种排序算法
- 鸽巢排序
  - 时间复杂度：
    - 最坏时间复杂度：$O(N+n)$。
    - 最好时间复杂度：$O(N+n)$。
  - 基本思路：假设我们要排序的数组为 init_array，设其中最大元素为 Max。额外分配一个长度为 Max 的 int 类型数组 temp[Max]，数组中元素初始都为 0，算法开始循环地将 temp 中下标为 init_array[i] 处的元素置一个常数 a（假设为 1）；然后从 0 开始扫描数组 init_array，遇到 temp 中值为这个常数 a 的元素时，将其依次存入数组 init_array 中，此时 init_array 中存储的就是已排序的元素。
  - 算法过程：
    1. 对于给定的一组要排序的数组，需要初始化一个空的辅助数组（“鸟巢”）,把初始数组中的每个值作为一个 key（“阁子”）。
    2. 遍历初始数组，根据每个值放入辅助数组对应的“阁子”。
    3. 顺序遍历辅助数组，把辅助数组“阁子”中不为空的数放回初始数组中。