algorithm - 迭代 k 层深度循环嵌套的时间复杂度总是 Θ(nᵏ)？

Question

许多算法中都有如下所示的循环：

for a from 1 to n
  for b from 1 to a
    for c from 1 to b
      for d from 1 to c
        for e from 1 to d
           ...
           // Do O(1) work

换句话说，循环嵌套是 k 层深，外层从 1 循环到 n，每个内层从 1 循环到它上面的索引。例如，这显示在迭代数组内所有位置的 k 元组的代码中。

假设 k 是固定的，那么这段代码的运行时间是否总是 Θ(n ^k )？对于 n = 1 的特殊情况，工作是 Θ(n)，因为它只是一个数组上的标准循环，对于 n = 2 的情况，工作是 Θ(n ² )，因为内部循环完成的工作是（谁）给的

0 + 1 + 2 + ... + n-1 = n(n-1)/2 = Θ(n ² )

当 k 变大时，这种模式会继续吗？还是只是巧合？

Answer 1

是的，时间复杂度将是 Θ(n ^k )。衡量此代码复杂性的一种方法是查看它生成的值。一个特别有用的观察是这些循环将遍历数组 {1, 2, 3, ..., n} 的所有可能的 k 元素子集，并且将花费 O(1) 时间来生成它们中的每一个。因此，我们可以说运行时间是由此类子集的数量给出的。给定一个 n 元素集合，k 元素子集的数量为 n 选择 k，等于

嗯！/k!(n - k)!

这是由

n (n-1)(n-2) ... (n - k + 1) / k！

这个值肯定不大于这个：

n · n · n · ... · n / k！（有 k 个 n 的副本）

= n ^k / k！

这个表达式是 O(n ^k )，因为 1/k! 项是一个固定常数。

同样，当 n - k + 1 ≥ n / 2 时，这个表达式大于等于

(n / 2) · (n / 2) · ... · (n / 2) / k！（有 k 个 n/2 副本）

= n ^k / k！2^千

这是 Ω(n ^k )，因为 1 / k！2 ^k是一个固定常数。

由于运行时间是 O(n ^k ) 和 Ω(n ^k )，所以运行时间是 Θ(n ^k )。

希望这可以帮助！

Answer 2

您可以使用以下等式：

其中c是最内层循环内的常数时间操作数，n是元素数，r是嵌套循环数。