多项式时间近似方案我们可以找到一些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)}大Ω符号大Ω… 阅读更多

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

此算法用于以螺旋形方式打印数组元素。首先从第一行开始，打印整个内容，然后沿着最后一列打印，然后是最后一行，依此类推，从而以螺旋形方式打印元素。此算法的时间复杂度为 O(MN)，其中 M 是行数，N 是列数。输入和输出输入：矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 输出：矩阵内容… 阅读更多

此算法将获取一个数组并洗牌数组的内容。它将生成数组元素的随机排列。为了解决这个问题，我们将从最后一个索引开始交换元素，以随机生成数组中的索引。输入和输出输入：一个整数数组：{1, 2, 3, 4, 5, 6, 7, 8} 输出：数组内容的洗牌：3 4 7 2 6 1 5 8（下次运行输出可能会有所不同）算法randomArr(array, n)输入：数组，元素数量。输出：洗牌数组的内容。开始    对于 i := n – 1 到 1，执行   ... 阅读更多

幻方是一个方阵，其阶数为奇数，并且每行、每列或每条对角线的元素之和都相同。每行、每列或每条对角线的和可以使用以下公式计算。n(n2+ 1)/2以下是构建幻方的规则：我们将从矩阵第一行的中间列开始，并始终转到左上角放置下一个数字如果行超出，或行不在矩阵中，则将列更改为左列并… 阅读更多

给定字符串列表按字母数字顺序或字典顺序排序。例如，对于以下单词：Apple、Book、Aim，它们将按 Aim、Apple、Book 的顺序排序。如果有一些数字，则可以将它们放在字母字符串之前。输入和输出输入：一个字符串列表：Ball Apple Data Area 517 April Man 506 输出：排序后的字符串：506 517 Apple April Area Ball Data Man算法sortStr(strArr, n)输入：所有字符串的列表，元素数量。输出 - 按字母数字排序的字符串。开始    对于 round := 1 到 n-1，执行       对于 i := 0 到 n-round，执行     ... 阅读更多

蔡勒公式用于根据给定日期查找星期几。使用蔡勒公式查找星期几的公式如下：公式包含一些变量；它们是 -d - 日期的天数。m：它是月份代码。从 3 月到 12 月，它是 3 到 12，对于 1 月，它是 13，对于 2 月，它是 14。当我们考虑 1 月或 2 月时，则给定的年份将减少 1。y - 年份的后两位数字c - 年份的前两位数字w - 星期几。当它为 0 时，是星期六，当... 阅读更多