javascript - 具有两个嵌套循环的循环的时间复杂度？

Question

我明白

var arr;  // This is an array of arrays 

for (i = 0; i < arr.length; i++)
{

  for(j = 0; j < arr[i].length; j++)
  {
   // Some code
  }
} 

是n^2，但是我下面的代码是一个双重嵌套的for循环，我只是好奇这种类型的函数的复杂性是什么样的

var arr;  // This is an array of arrays


for (i = 0; i < arr.length; i++)
{

  for(j = 0; j < arr[i].length; j++)
  {
   // Some code
  }

  for(k = 0; k < arr[i].length; k++)
  {
   // Some code
  }
} 

Answer 1

连续代码段的复杂度是其中每段代码的最大复杂度。因此，如果您有两个连续的循环，并且它们都是 O(n)，那么两者的复杂度合计也是 O(n)。

由于这两个循环嵌套在 O(n) 循环中，因此整个过程的复杂度为 O(n^2)。就像原始代码的复杂性一样。