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，等于

n! / k!(n - k)!

这是由

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

这个值肯定不会大于这个:

n · n · n · ... · n / k! (with k copies of n)

= n^k / k!

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

同理，当n - k + 1 ≥ n/2时，此表达式大于等于

(n / 2) · (n / 2) · ... · (n / 2) / k! (with k copies of n/2)

= n^k / k! 2^k

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

由于运行时间为 O(n^k) 和 Ω(n^k)，因此运行时间为 Θ(n^k)。

希望这对您有所帮助!