在算法的理论分析中，通常以渐近意义估计其复杂度，即对任意大的输入估计复杂度函数。“算法分析”一词由 Donald Knuth 创造。算法分析是计算复杂性理论的重要组成部分，它为解决特定计算问题所需的算法资源提供理论估计。大多数算法设计用于处理任意长度的输入。算法分析是确定执行算法所需的时间和空间资源量。通常，算法的效率或运行时间… 阅读更多

图是一种非线性数据结构，它由有限数量的节点和一组用于连接节点对的边组成。图用于解决一些实时问题，例如表示网络等。在不同的社交网络中，都使用图。在本节中，我们将介绍 - 双连通图检查、图的广度优先搜索 (BFS)、图中的桥梁、检查给定图是否是树、有向图中的连通性、图的深度优先搜索 (DFS)、检测无向图中的循环、检测… 阅读更多

搜索算法用于从数据集中搜索或查找一个或多个元素。这类算法用于从特定数据结构中查找元素。搜索可以是顺序的，也可以不是顺序的。如果数据集中数据是随机的，则需要使用顺序搜索。否则，可以使用其他不同的技术来降低复杂度。在本节中，我们将介绍 - 二分查找、指数查找、插值查找、跳跃查找、线性查找、三元查找。

模式搜索算法用于从另一个更大的字符串中查找模式或子字符串。存在不同的算法。设计这类算法的主要目标是降低时间复杂度。对于较长的文本，传统方法可能需要大量时间才能完成模式搜索任务。在这里，我们将看到不同的算法，以获得更好的模式匹配性能。在本节中，我们将介绍：Aho-Corasick 算法、字谜模式搜索、不良字符启发式算法、Boyer Moore 算法、有限自动机的有效构造、kasai 算法、Knuth-Morris-Pratt 算法、Manacher 算法、朴素模式搜索、Rabin-Karp… 阅读更多

我们在不同的章节中看到了不同的问题。还有一些其他问题没有分类。在本节中，我们将看到一些随机问题。在本节中，我们将介绍：添加 n 进制数、巴比伦法求平方根、大数阶乘、检查给定点是否在多边形内、检查完全平方数、检查给定的四个点是否构成正方形、检查两个给定集合是否不相交、检查两条线段是否相交、检查给定点是否在三角形内、连接 n 条绳子… 阅读更多

回溯是一种增量式解决问题的算法技术。它使用递归方法来解决问题。可以说，回溯用于查找所有可能的组合来解决优化问题。在本节中，我们将介绍：哈密顿循环、M 着色问题、N 皇后问题、迷宫老鼠问题、密码算术难题、子集和问题、数独求解算法、骑士巡游问题、拔河问题、单词拆分算法、交换得到最大数问题。

多项式时间近似方案我们可以找到一些 NP 完全问题的多项式时间解，例如 0-1 背包问题或子集和问题。这些问题在现实世界中非常流行，因此必须有一些方法来处理这些问题。多项式时间近似方案 (PTAS) 是一种用于优化问题的近似算法。对于 0-1 背包问题，存在一个伪多项式解，但是当值很大时，该解不可行。然后我们需要一个 PTAS 解。一些 NP 完全问题，如图着色、K 中心问题等，它们没有已知的多项式时间解。PTAS 用于近似… 阅读更多

空间复杂度空间复杂度是算法（包括算法的输入值）为完全执行并产生结果而使用的内存量。我们知道，要执行算法，必须将其加载到主内存中。内存可以使用不同的形式：变量（包括常量和临时值）、程序指令、执行、辅助空间。辅助空间是算法在其执行过程中使用的额外空间或临时空间。程序执行期间的内存使用情况：指令空间用于在内存中保存编译后的指令。环境堆栈用于在模块调用另一个模块时存储地址… 阅读更多

均摊分析这种分析方法用于处理偶尔出现非常慢的操作，但大多数频繁执行的操作速度很快的情况。需要均摊分析的数据结构包括哈希表、不相交集等。在哈希表中，大多数情况下搜索时间复杂度为 O(1)，但有时会执行 O(n) 的操作。当我们想要搜索或插入哈希表中的元素时，大多数情况下是常数时间，但发生冲突时，需要 O(n) 时间来解决冲突。聚合方法聚合方法用于查找……阅读更多

渐近记号渐近记号用于表示算法在渐近分析中的复杂度。这些记号是表示复杂度的数学工具。常用的记号有三种。大O记号大O (O) 记号给出了函数 f(n) 的上限，精度到常数因子。我们写 f(n) = O(g(n))，如果存在正的常数 n0 和 c，使得在 n0 右侧，f(n) 始终位于或低于 c*g(n)。O(g(n)) = { f(n) : 存在正常数 c 和 n0，使得 0 ≤ f(n) ≤ c g(n)，对于所有 n ≥ n0}大Ω记号大Ω……阅读更多