Блог

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

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

#javascript #algorithm #big-o

#javascript #алгоритм #big-o

Вопрос:

Я понимаю, что

 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
  }
}

Комментарии:

1. Это то же самое. Вы только что умножили на постоянный коэффициент, и это никак не влияет на сложность.

2. Сложность все та же, но ваша аналогия с n ^ 2 верна, если все столбцы имеют ту же длину, что и строки, иначе сложность равна rows * columns

3. Если вы выполните поиск по фразе «Как вычислить временную сложность алгоритма», вы найдете ресурсы, которые могут объяснить это намного лучше, чем мы можем в ответе здесь.

Ответ №1:

Сложность последовательных фрагментов кода — это максимальная сложность каждого из них. Итак, если у вас есть два последовательных цикла, и они оба O(n) , то сложность обоих вместе также O(n) .

Поскольку эти два цикла вложены внутри O(n) цикла, сложность всего этого O(n^2) . Точно так же, как сложность исходного кода.

Ответ №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²)