3个嵌套for循环的运行时间，其中最内层循环取决于外层循环中的操作（不是明显的情况）

Question

我是一个初学者，第一次在这里学习算法。我想知道以下具有 3 个嵌套 for 循环的算法的运行时间。我知道在大多数情况下，它是循环长度的乘积。然而，在这种情况下，最内层循环的长度取决于循环外部的操作。

def loops(n,k){
  exp = 1;
  for (i=0; i<n; i++){
    newexp =0;
    for (j=0; j<k; j++){
      for (q =0; q<exp; q++){
        newexp++;
      }
    }
    exp = newexp;
  }
  return exp;
}

我的猜测是，由于

exp

对于 i 的每次迭代都会呈指数增长，因此它的复杂度为 O(n*k*(k^n))。我说得对吗？任何解释将不胜感激。谢谢大家！！

Answer 1

首先对伪代码进行一些注释：

• a

  未使用，因此不需要作为参数。

• k

  没有任何定义；它可能应该是一个参数，因为您也将它用作复杂性计算中的变量。

这是一个图表，其中外循环的每次迭代都有一行，以及执行

exp = newexp;

之前的状态

𝑖	𝑒𝑥𝑝	𝑛𝑒𝑤𝑒𝑥𝑝 := 𝑒𝑥𝑝∙𝑘	总计
0	1	𝑘	𝑘
1	𝑘	𝑘²	𝑘+𝑘²
2	𝑘²	𝑘³	𝑘+𝑘²+𝑘³
...	...	...	....
𝑛−1	𝑘𝑛−1	𝑘𝑛	Σ𝑖=1..𝑛 𝑘𝑖

最后一列表示执行

newexp++

的次数，这是当𝑛和𝑘无限增长时渐近复杂性的决定因素。累积值代表几何级数的总和（没有第一项1），并且是：

      (𝑘^𝑛+1−1) / (𝑘−1) − 1

这是O(𝑘^𝑛)