任意嵌套for循环的Big-O分析？

Question

假设我有 k 个 for 循环以下列方式嵌套:

for a = 1 to n:
    for b = 1 to n-a:
        for c = 1 to n-a-b:
            for d = 1 to n-a-b-c:
                O(1)

对于任意 k 个，但所有 k 个循环彼此“共享”n 次迭代的限制，big-O 复杂度是否仍然为 O(n^k)？还是低于该顺序？

编辑:What is the Big-O of a nested loop, where number of iterations in the inner loop is determined by the current iteration of the outer loop?确实在问类似的问题，但它没有问(也没有回答地址)额外的嵌套级别是否会改变任何东西。

德米特里的回答对我来说解释得很好。

Answer 1

好的，让我们总结一下:使用归纳法，您可以发现循环数(对于较大的n > k)是:

  1. n 
  2. n * (n - 1) / 2 
  3. n * (n - 1) * (n - 2) / 6
  ...
  k. n * (n - 1) * ... * (n - k + 1) / k!
  ...

如您所见，复杂度为 O(n**k)，正如您为任何 k 所设想的那样，前提是 n 是足够大 (n > k)。