二、算法
1.分治算法（Divide and Conquer）
分而治之（DAC）本身并不是一个特定的算法，而是在深入研究其他主题之前需要了解的重要算法类别。它用于解决可以划分为与原始问题相似但规模较小的子问题的问题。然后 DAC 递归地求解它们，最后合并结果以找到问题的解决方案。
它分为三个阶段：
划分——将问题分解为子问题；
用递归解决子问题；
合并——子问题的结果到最终解决方案中。
它是干什么用的？
分治算法（DAC） 的一种实际应用是使用多个处理器进行并行编程，因此子问题在不同的机器上执行。
DAC 是许多算法的基础，例如快速排序、合并排序、二分搜索或快速乘法算法。
特性
每个 DAC 问题都可以写成一个递推关系；因此，必须找到停止递归的基本情况；
它的复杂度是T(n)=D(n)+C(n)+M(n)，这意味着每个阶段都有不同的复杂度，具体取决于问题。
2. 排序算法（Sorting Algorithms）
排序算法用于根据元素上的比较运算符重新排列给定元素（来自数组或列表）。当我们提到一个排序数组时，我们通常会想到升序（比较运算符是“<”）。排序有多种类型，具有不同的时间和空间复杂度。其中一些是基于比较的，有些则不是。以下是最流行/最有效的排序方法：
冒泡排序（Bubble Sort）
冒泡排序是最简单的排序算法之一。它基于相邻元素之间的重复交换（如果它们的顺序错误）。它是稳定的，它的时间复杂度是 O(n²) 并且它需要 O(1) 辅助空间。
计数排序（Counting Sort）
计数排序不是基于比较的排序。它基本上是使用每个元素的频率（一种散列），确定最小值和最大值，然后在它们之间迭代以根据其频率放置每个元素。它在 O(n) 中完成，空间与数据范围成正比。如果输入范围不明显大于元素数量，则它是有效的。
快速排序（Quick Sort）
快速排序是分而治之的一个应用。它基于选择一个元素作为枢轴（第一个、最后一个或中间值），然后交换元素以将枢轴放置在所有小于它的元素和所有大于它的元素之间。它没有额外的空间和 O(n*log n) 时间复杂度——基于比较的方法的最佳复杂度。
归并排序（Merge Sort）
归并排序也是一个分而治之的应用程序。它将数组分成两半，对每一半进行排序，然后合并它们。它的时间复杂度也是 O(n*log n)，所以它也像 Quick Sort 一样超快，但不幸的是它需要 O(n) 额外空间来同时存储两个子数组，最后合并它们。
基数排序（Radix Sort）
基数排序使用计数排序作为子程序，因此它不是基于比较的算法。我们怎么知道CS是不够的？假设我们必须对[1, n²] 中的元素进行排序。使用 CS，我们需要 O(n²)。我们需要一个线性算法——O(n+k)，其中元素在[1, k]范围内。它从最不重要的一个（单位）开始，到最重要的（十、百等）对元素进行逐位排序。额外空间（来自 CS）：O(n)。
3. 搜索算法（Searching Algorithms）
搜索算法旨在检查数据结构中元素的存在，甚至返回它。有几种搜索方法，但这里是最受欢迎的两种：
线性搜索（Linear Search）
该算法的方法非常简单：您从数据结构的第一个索引开始搜索您的值。您将它们一一比较，直到您的值和当前元素相等。如果该特定值不在 DS 中，则返回 -1。
时间复杂度：O(n)
二分查找（Binary Search）
BS 是一种基于分而治之的高效搜索算法。不幸的是，它只适用于排序的数据结构。作为一种 DAC 方法，您连续将 DS 分成两半，并将搜索中的值与中间元素的值进行比较。如果它们相等，则搜索结束。无论哪种方式，如果您的值大于/小于它，搜索应该继续在右/左半部分。
时间复杂度：O(log n)
4. 埃氏筛法（Sieve of Eratosthenes）
给定一个整数 n，打印所有小于或等于 n 的素数。
Eratosthenes 筛法是解决这个问题的最有效的算法之一，它完美地适用于小于10.000.000 的n 。
该方法使用频率列表/映射来标记[0, n]范围内每个数字的素数：如果 x 是素数，则ok[x]=0，否则ok[x]=1。
我们开始从列表中选择每个素数，并用 1 标记列表中的倍数——这样，我们选择未标记的 (0) 数。最后，我们可以在 O(1) 中轻松回答任意数量的查询。
经典算法在许多应用中都是必不可少的，但我们可以进行一些优化。首先，我们很容易注意到 2 是唯一的偶素数，因此我们可以单独检查它的倍数，然后在范围内迭代以找到从 2 到 2 的素数。其次，很明显，对于数字 x，我们之前在迭代 2、3 等时已经检查了 2x、3x、4x 等。这样，我们的乘数检查 for 循环每次都可以从 x² 开始。最后，即使这些倍数中有一半是偶数，而且我们也在迭代奇素数，因此我们可以在倍数检查循环中轻松地从 2x 迭代到 2x。
空间复杂度：O(n)
时间复杂度：O(n*log(log n)) 用于经典算法，O(n) 用于优化算法。
5. 字符串匹配算法（Knuth-Morris-Pratt）
给定长度为 n 的文本和长度为 m 的模式，找出文本中所有出现的模式。
Knuth-Morris-Pratt 算法 (KMP) 是解决模式匹配问题的有效方法。
天真的解决方案基于使用“滑动窗口”，每次设置新的起始索引时，我们都会比较字符与字符，从文本的索引 0 开始到索引 nm。这样，时间复杂度是 O(m*(n-m+1))~O(n*m)。
KMP 是对朴素解决方案的优化：它在 O(n) 中完成，并且当模式具有许多重复的子模式时效果最佳。因此，它也使用滑动窗口，但不是将所有字符与子字符串进行比较，而是不断寻找当前子模式的最长后缀，这也是它的前缀。换句话说，每当我们在某些匹配后检测到不匹配时，我们就已经知道下一个窗口文本中的某些字符。因此，再次匹配它们是没有用的，因此我们重新开始匹配文本中具有该前缀后的字符的相同字符。我们怎么知道我们应该跳过多少个字符？好吧，我们应该构建一个预处理数组，告诉我们应该跳过多少个字符。
6.贪婪算法（Greedy）
Greedy 方法多用于需要优化且局部最优解导致全局最优解的问题。
也就是说，当使用 Greedy 时，每一步的最优解都会导致整体最优解。然而，在大多数情况下，我们在一个步骤中做出的决定会影响下一步的决定列表。在这种情况下，必须用数学方法证明算法。Greedy 也会在一些数学问题上产生很好的解决方案，但不是全部（可能无法保证最佳解决方案）！
贪心算法通常有五个组成部分：
候选集——从中创建解决方案；
选择函数——选择最佳候选人；
可行性函数——可以确定候选人是否能够为解决方案做出贡献；
一个目标函数——将候选人分配给（部分）解决方案；
一个解决方案函数——从部分解决方案构建解决方案。
分数背包问题
给定n个物品的重量和价值，我们需要将这些物品放入容量为W的背包中，以获得背包中的最大总价值（允许取件物品：一件物品的价值与其重量成正比）。
贪心方法的基本思想是根据它们的价值/重量比对所有项目进行排序。然后，我们可以添加尽可能多的整个项目。当我们发现一件比背包中剩余重量 (w1) 重 (w2) 的物品时，我们将对其进行分割：仅取出w2-w1以最大化我们的利润。保证这个贪心的解决方案是正确的。
7. 动态规划（Dynamic Programming）
动态规划 (DP) 是一种类似于分而治之的方法。它还将问题分解为类似的子问题，但它们实际上是重叠和相互依赖的——它们不是独立解决的。
每个子问题的结果都可以在以后随时使用，它是使用记忆（预先计算）构建的。DP 主要用于（时间和空间）优化，它基于寻找循环。
DP 应用包括斐波那契数列、河内塔、Roy-Floyd-Warshall、Dijkstra 等。 下面我们将讨论 0-1 背包问题的 DP 解决方案。
0–1 背包问题
给定n个物品的重量和价值，我们需要将这些物品放入容量为W的背包中，以获得背包中的最大总值（不允许像贪婪解决方案中的那样分割物品）。
0-1 属性是由我们应该选择整个项目或根本不选择它的事实给出的。
我们构建了一个 DP 结构作为矩阵dp[i][cw]存储我们通过选择总权重为 cw 的 i 个对象可以获得的最大利润。很容易注意到我们应该首先用v[i]初始化dp[1][w[i] ]，其中w[i]是第 i 个对象的权重，v[i] 是它的值。
复现如下：
dp[i][cw] = max(dp[i-1][cw], dp[i-1][cw-w[i]]+v[i])
1
我们稍微分析一下。
dp[i-1][cw]描述了我们没有在背包中添加当前物品的情况。dp[i-1][cw-w[i]]+v[i]就是我们添加item的情况。话虽如此，dp[i-1][cw-w[i]]是采用 i-1 个元素的最大利润：所以它们的重量是当前重量，没有我们的物品重量。最后，我们将项目的值添加到它。
答案存入dp[n][W]. 通过一个简单的观察进行优化：在循环中，当前行仅受前一行的影响。因此，将DP结构存储到矩阵中是不必要的，因此我们应该选择一个空间复杂度更好的数组：O(n)。时间复杂度：O(n*W)。
8. 最长公共子序列（Longest Common Subsequence）
给定两个序列，找出它们中存在的最长子序列的长度。子序列是以相同的相对顺序出现的序列，但不一定是连续的。例如，“bcd”、“abdg”、“c”都是“abcdefg”的子序列。
这是动态规划的另一个应用。LCS 算法使用 DP 来解决上述问题。
实际的子问题是要分别从序列 A 中的索引 i 开始，分别从序列 B 中的索引 j 中找到最长公共子序列。
接下来，我们将构建 DP 结构lcs[ ][ ]（矩阵），其中lcs[i][j]是从 A 中的索引 i 开始，分别是 B 中的索引 j 的公共子序列的最大长度。我们将以自顶向下的方式构建它。显然，解决方案存储在lcs[n][m] 中，其中 n 是 A 的长度，m 是 B 的长度。
递推关系非常简单直观。为简单起见，我们将考虑两个序列都是 1 索引的。首先，我们将初始化lcs[i][0] , 1<=i<=n和lcs[0][j] , 1<=j<=m , 0, 作为基本情况（没有从 0 开始的子序列）。然后，我们将考虑两种主要情况：如果A[i]等于B[j]，则lcs[i][j] = lcs[i-1][j-1]+1（比之前的 LCS 多一个相同的字符）。否则，它将是lcs[i-1][j]（如果不考虑A[i]）和lcs[i][j-1]（如果不考虑B[j]）之间的最大值）。
时间复杂度：O(n*m)
附加空间：O(n*m)
9. 最长递增子序列（Longest Increasing Subsequence）
给定一个包含 n 个元素的序列 A，找到最长子序列的长度，使其所有元素按递增顺序排序。子序列是以相同的相对顺序出现的序列，但不一定是连续的。例如，“bcd”、“abdg”、“c”是“abcdefg”的子序列。
LIS 是另一个可以使用动态规划解决的经典问题。
使用数组l[ ]作为 DP 结构来寻找递增子序列的最大长度，其中l[i]是包含A[i]的递增子序列的最大长度，其元素来自[A[i] ], ..., A[n]] 子序列。l[i]为 1，如果A[i]之后的所有元素比它小。否则，在 A[i] 之后大于它的所有元素之间的最大值为 1+。显然，l[n]=1，其中 n 是 A 的长度。 实现是自底向上的（从末尾开始）。
在搜索当前元素之后的所有元素之间的最大值时出现了一个优化问题。我们能做的最好的事情是二分搜索最大元素。
为了找到现在已知的最大长度的子序列，我们只需要使用一个额外的数组ind[]，它存储每个最大值的索引。
时间复杂度：O(n*log n)
附加空间：O(n)
10.凸包算法（Convex Hull）
给定同一平面中的一组 n 个点，找到包含所有给定点（位于多边形内部或其边上）的最小面积凸多边形。这种多边形称为凸包。凸包问题是一个经典的几何，在现实生活中有很多应用。例如，碰撞避免：如果汽车的凸包避免碰撞，那么汽车也能避免碰撞。路径的计算是使用汽车的凸表示完成的。形状分析也是在凸包的帮助下完成的。这样，图像处理很容易通过匹配模型的凸缺陷树来完成。
有一些算法用于寻找凸包，如 Jarvis 算法、Graham 扫描等。今天我们将讨论 Graham 扫描和一些有用的优化。
格雷厄姆扫描按极角对点进行排序——由某个点和其他选定点确定的线的斜率。然后用一个栈来存储当前时刻的凸包。当一个点 x 被压入堆栈时，其他点会被弹出堆栈，直到 x 与最后两个点所确定的线形成小于 180° 的角度。最后，引入堆栈的最后一个点关闭多边形。由于排序，这种方法的时间复杂度为 O(n*log n)。但是，这种方法在计算斜率时会产生精度误差。
一种改进的解决方案具有相同的时间复杂度，但误差较小，按坐标（x，然后是 y）对点进行排序。然后我们考虑由最左边和最右边的点形成的线，并将问题分为两个子问题。最后，我们在这条线的每一边找到了凸包。所有给定点的凸包是两个包的重聚。
11. 图遍历（Graph Traversals）
遍历图的问题是指以特定顺序访问所有节点，通常沿途计算其他有用信息。
广度优先搜索（Breadth-First Search）
广度优先搜索 (BFS) 算法是确定图是否连通的最常用方法之一——或者换句话说，查找 BFS 源节点的连通分量。
BFS 还用于计算源节点和所有其他节点之间的最短距离。BFS 的另一个版本是 Lee 算法，用于计算网格中两个单元格之间的最短路径。
该算法首先访问源节点，然后访问将被推入队列的邻居。队列中的第一个元素被弹出。我们将访问它的所有邻居，并将之前未访问的邻居推入队列。重复该过程直到队列为空。当队列为空时，表示所有可达顶点都已访问完毕，算法结束。
深度优先搜索（Depth-First Search）
深度优先搜索 (DFS) 算法是另一种常见的遍历方法。在检查图形的连通性时，它实际上是最好的选择。
首先，我们访问根节点并将其压入堆栈。虽然堆栈不为空，但我们检查顶部的节点。如果该节点有未访问的邻居，则选择其中一个并将其压入堆栈。否则，如果它的所有邻居都被访问过，我们就会弹出这个节点。当堆栈变空时，算法结束。
经过这样的遍历，就形成了一个DFS树。DFS 树有很多应用；最常见的一种是存储每个节点的“开始”和“结束”时间——它进入堆栈的时刻，分别是它从堆栈中弹出的时刻。
12. 弗洛依德算法（Floyd-Warshall）
Floyd-Warshall / Roy-Floyd 算法解决了所有对最短路径问题：找到给定边加权有向图中每对顶点之间的最短距离。
FW 是一个动态规划应用程序。DP 结构（矩阵）dist[ ][ ]用输入图矩阵初始化。然后我们将每个顶点视为其他两个节点之间的中间体。最短路径在每两对节点之间更新，任何节点 k 作为中间顶点。如果 k 是 i 和 j 之间排序路径中的中间值，则dist[i][j]成为dist[i][k]+dist[k][j]和dist[i][j]之间的最大值。
时间复杂度：O(n³)
空间复杂度：O(n²)
13. Dijkstra 算法和 Bellman-Ford 算法
迪杰斯特拉（Dijkstra） 算法
给定一个图和图中的一个源顶点，找出从源到给定图中所有顶点的最短路径。
Dijkstra 算法用于在加权图中找到这样的路径，其中所有的权重都是正的。
Dijkstra 是一种贪心算法，它使用以源节点为根的最短路径树（SPT）。SPT 是一种自平衡二叉树，但该算法可以使用堆（或优先级队列）来实现。我们将讨论堆解决方案，因为它的时间复杂度是 O(|E|*log |V|)。这个想法是使用图形的邻接列表表示。这样，节点将使用 BFS （广度优先搜索）在 O(|V|+|E|) 时间内遍历。
所有顶点都用 BFS 遍历，那些最短距离尚未最终确定的顶点被存储到最小堆（优先队列）中。
创建最小堆并将每个节点连同它们的距离值一起推入其中。然后，源成为距离为 0 的堆的根。其他节点将无限分配为距离。当堆不为空时，我们提取最小距离值节点 x。对于与 x 相邻的每个顶点 y，我们检查 y 是否在最小堆中。在这种情况下，如果距离值大于 (x, y) 的权重加上 x 的距离值，那么我们更新 y 的距离值。
贝尔曼-福特（Bellman-Ford）算法
正如我们之前所说，Dijkstra 仅适用于正加权图。贝尔曼解决了这个问题。给定一个加权图，我们可以检查它是否包含负循环。如果没有，那么我们还可以找到从我们的源到其他源的最小距离（可能为负权重）。
Bellman-Ford 非常适合分布式系统，尽管它的时间复杂度是 O(|V| |E|)。
我们初始化一个 dist[] 就像在 Dijkstra 中一样。对于 *|V|-1次，对于每个(x, y)边，如果dist[y] > dist[x] + (x, y) 的权重，那么我们用它更新dist[y]。
我们重复最后一步以可能找到负循环。这个想法是，如果没有负循环，最后一步保证最小距离。如果有任何节点在当前步骤中的距离比上一步中的距离短，则检测到负循环。
14.克鲁斯卡尔算法（Kruskal’s Algorithm）
我们之前已经讨论过什么是最小生成树。
有两种算法可以找到图的 MST：Prim（适用于密集图）和 Kruskal（适用于大多数图）。现在我们将讨论 Kruskal 算法。
Kruskal 开发了一种贪心算法来寻找 MST。它在稀有图上很有效，因为它的时间复杂度是 O(|E|*log |V|)。
该算法的方法如下：我们按权重的递增顺序对所有边进行排序。然后，选取最小的边。如果它不与当前 MST 形成循环，我们将其包括在内。否则，丢弃它。重复最后一步，直到 MST 中有 |V|-1 条边。
将边包含到 MST 中是使用 Disjoint-Set-Union 完成的，这也在前面讨论过。
15. 拓扑排序（Topological Sorting）
有向无环图 (DAG) 只是一个不包含循环的有向图。
DAG 中的拓扑排序是顶点的线性排序，使得对于每个拱形(x, y)，节点 x 出现在节点 y 之前。
显然，拓扑排序中的第一个顶点是一个入度为 0 的顶点（没有拱形指向它）。
另一个特殊属性是 DAG 没有唯一的拓扑排序。
BFS （广度优先搜索）实现遵循此例程：找到一个入度为 0 的节点并将第一个推入排序。该顶点已从图中删除。由于新图也是一个 DAG，我们可以重复这个过程。
在 DFS 期间的任何时候，节点都可以属于以下三个类别之一：
我们完成访问的节点（从堆栈中弹出）；
当前在堆栈上的节点；
尚未发现的节点。
如果在 DAG 中的 DFS 期间，节点 x 具有到节点 y 的输出边，则 y 属于第一类或第三类。如果 y 在堆栈上，则(x, y)将结束一个循环，这与 DAG 定义相矛盾。
这个属性实际上告诉我们一个顶点在它的所有传出邻居都被弹出后从堆栈中弹出。因此，要对图进行拓扑排序，我们需要跟踪弹出顶点的逆序列表。
