任意嵌套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 个循环 "share" 相互迭代 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!
  ...

如您所见，如果 n 足够大 (n > k)，那么复杂度是 O(n**k)，正如您对任何 k 所想象的那样。

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

Big-O Analysis of Arbitrarily Nested For Loops?

big-o