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)。

希望这有帮助!