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

渐近记号渐近记号用于表示算法在渐近分析中的复杂度。这些记号是表示复杂度的数学工具。常用的记号有三种。大O记号大O (O) 记号为函数 f(n) 提供了一个上限，精确到一个常数因子。小o记号除了大O、大Ω和大θ记号外，还有一些其他记号。小o记号就是其中之一。小o记号用于描述一个不能收紧的上限。换句话说，它是f(n)的松散上限。大Ω记号大Ω (Ω) 记号为… 阅读更多

渐近分析使用渐近分析，我们可以根据输入大小了解算法的性能。我们不应该计算精确的运行时间，而应该找到运行时间和输入大小之间的关系。当输入大小增加时，我们应该关注运行时间。对于空间复杂度，我们的目标是得到一个关系或函数，说明为了完成算法，主内存中占用了多少空间。渐近行为对于函数 f(n)，渐近行为是 f(n) 在 n 变大的情况下的增长情况。较小的输入值… 阅读更多

在算法的理论分析中，通常以渐近的方式估计它们的复杂度，即估计任意大输入的复杂度函数。“算法分析”一词由唐纳德·克努特提出。算法分析是计算复杂性理论的重要组成部分，它为解决特定计算问题所需的算法资源提供了理论估计。大多数算法的设计都是为了处理任意长度的输入。算法分析是确定执行算法所需的时间和空间资源量。通常，算法的效率或运行时间… 阅读更多

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

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

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

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

算法算法是有限的一组指令，如果遵循这些指令，则可以完成特定任务。它不是特定于语言的，我们可以使用任何语言和符号来表示指令。算法的标准输入：零个或多个输入由外部提供给算法。输出：算法至少产生一个输出。确定性：每个指令都清晰明确。有限性：在一个算法中，它将在所有不同情况下经过有限步骤后终止。有效性：每个指令都必须非常基本，因此这些指令的目的必须对我们非常清晰。算法分析算法分析是… 阅读更多

进程 爆发时间 A 4 B 1 C 8 D 1 时间片=10 单位 A B C D A C C C 0 2 3 5 6 8 10 12 14 所以 A 将完成 8 个周期。