跳转至

算法中的名词解释

增长量级：算法的时间复杂度和空间复杂度表达式中项的系数和常数因子被忽略，剩下只保留最高阶项的符号，这种表示方法称为渐进表示法，记作O(f(n))，称为算法的增长量级。

渐进记号：是用于描述算法在输入规模趋于无穷大时的性能的数学工具。它们帮助我们理解算法的运行时间或空间需求的增长趋势。常见的渐进记号包括：

  1. 大O记号 (O)：表示算法的上界，即算法的运行时间或空间需求不会超过这个界限。形式上，如果存在正常数 和 ，使得对于所有 ，有 ，则称 。

  2. 大Ω记号 (Ω)：表示算法的下界，即算法的运行时间或空间需求至少达到这个界限。形式上，如果存在正常数 和 ，使得对于所有 ，有 ，则称 。

  3. 大Θ记号 (Θ)：表示算法的紧界，即算法的运行时间或空间需求既不会超过也不会低于这个界限。形式上，如果存在正常数 、 和 ，使得对于所有 ，有 ，则称 。

  4. 小o记号 (o)：表示算法的上界，但这个上界不是紧的，即算法的运行时间或空间需求远小于这个界限。形式上，如果对于任意正常数 ，存在 ，使得对于所有 ，有 ，则称 。

  5. 小ω记号 (ω)：表示算法的下界，但这个下界不是紧的，即算法的运行时间或空间需求远大于这个界限。形式上，如果对于任意正常数 ，存在 ，使得对于所有 ，有 ，则称 。

增长量级是描述函数增长速度的术语，通常与渐进记号一起使用。例如，如果一个函数 的增长量级是 ，我们可以说 或 ，具体取决于 的确切行为。

总结来说，渐进记号提供了一种方式来比较和分类算法的性能，而增长量级是描述函数增长速度的术语。通过使用这些记号，我们可以更清楚地理解算法在处理大规模输入时的行为。

多重对数函数：例如， 的值，这里的 表示迭代对数（iterated logarithm），它是指对数函数的多次复合。具体来说， 表示对 应用对数函数直到结果小于或等于1的次数。

让我们计算 ：

  1. 首先计算 ：

  2. 然后计算 ：

  3. 接着计算 ：

  4. 最后计算 ：

我们看到，从16开始，应用对数函数3次后结果小于或等于1（具体来说，是1）。因此，。

的值是 。