Временная сложность для цикла с двумя вложенными циклами?

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, однако мой код ниже является циклом с двойным вложением, и мне просто интересно, как будет выглядеть сложность для этого типа функции

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). Так же, как сложность исходного кода.

Answer 2

Цикл имеет сложность O(n * content), блок операторов имеет сложность всех его добавленных элементов O(n1 + n2 + ...).Теперь в вашем случае это

// v outer loop
//      v inner loop 1
//                v inner loop 2
O(n * ((n * 1) + (n * 1)))
= O(n * (n + n))
= O(n * 2n) // constants can be ignored
= O(n * n)
= O(n²)