在算法的理论分析中，通常会在渐近意义上估计其复杂度，即估计任意大输入的复杂度函数。“算法分析”一词由 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，使得对于所有 n ≥ n0，0 ≤ f(n) ≤ c g(n)}大Ω记号大Ω……阅读更多