Временная сложность вложенного цикла for - PullRequest
Новая
       41

Временная сложность вложенного цикла for

25 голосов
/ 09 февраля 2009

Мне нужно вычислить временную сложность следующего кода: 

for (i = 1; i <= n; i++)
{
  for(j = 1; j <= i; j++)
  {
   // Some code
  }
}

Это O (n ^ 2) ?

Ответы [ 5 ]

42 голосов
/ 09 февраля 2009

Да, вложенные циклы - это один из способов быстро получить большие обозначения O.

Обычно (но не всегда) один цикл, вложенный в другой, вызывает O (n²).

Подумайте об этом, внутренний цикл выполняется i раз, для каждого значения i . Внешний цикл выполняется n раз.

таким образом, вы видите схему исполнения, подобную этой: 1 + 2 + 3 + 4 + ... + n раз

Следовательно, мы можем ограничить количество выполнений кода, сказав, что он, очевидно, выполняется более n раз (нижняя граница), но с точки зрения n, сколько раз мы выполняем код?

Ну, математически мы можем сказать, что он будет выполняться не более n² раз, что дает нам сценарий наихудшего случая и, следовательно, нашу оценку Big-Oh O (n²). (Для получения дополнительной информации о том, как мы можем математически выразить это, посмотрите на Power Series )

Big-Oh не всегда точно измеряет объем работы, но обычно дает надежное приближение к худшему сценарию.

4 года спустя Редактировать: Поскольку этот пост, похоже, получает достаточное количество трафика. Я хочу более полно объяснить, как мы связываем выполнение с O (n²), используя степенные ряды

С веб-сайта: 1 + 2 + 3 + 4 ... + n = (n² + n) / 2 = n² / 2 + n / 2. Как же тогда мы превращаем это в O (n²)? Мы (в основном) говорим, что n²> = n² / 2 + n / 2. Это правда? Давайте сделаем простую алгебру.

  • Умножьте обе стороны на 2, чтобы получить: 2n²> = n² + n?
  • Разверните 2n², чтобы получить: n² + n²> = n² + n?
  • Вычтите n² с обеих сторон, чтобы получить: n²> = n?

Должно быть ясно, что n²> = n (не строго больше, чем, из-за случая, когда n = 0 или 1), предполагая, что n всегда является целым числом.

Фактическая сложность Big O немного отличается от того, что я только что сказал, но это суть. В действительности сложность Big O спрашивает, существует ли константа, которую мы можем применить к одной функции, чтобы она была больше другой, для достаточно большого ввода (см. Страницу wikipedia )

24 голосов
/ 08 ноября 2014

Быстрый способ объяснить это - это визуализировать.

если i и j от 0 до N, легко увидеть O (N ^ 2) 

O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O

в данном случае это: 

O
O O
O O O
O O O O
O O O O O
O O O O O O
O O O O O O O
O O O O O O O O

Получается, что это 1/2 от N ^ 2, что по-прежнему равно O (N ^ 2)

9 голосов
/ 09 февраля 2009

Действительно, это O (n ^ 2). Смотрите также очень похожий пример с тем же временем выполнения здесь .

0 голосов
/ 17 апреля 2015

На 1-й итерации внешнего цикла (I = 1), то внутренний цикл будет повторять 1 раз На 2-й итерации внешнего цикла (I = 2), то внутренний цикл будет повторять 2 раз На 3-й итерации внешнего цикла (I = 3), внутренний цикл будет повторять 3 раза
.
.
На последней итерации внешнего цикла (I = N), то внутренний цикл будет итерация п раз

Таким образом, общее число раз операторы во внутреннем цикле будет выполняться будет равна сумме целых чисел от 1 до п, что: 

((n)*n) / 2 = (n^2)/2 = O(n^2) times
0 голосов
/ 29 апреля 2014

Сначала рассмотрим циклы, в которых число итераций внутреннего цикла не зависит от значения индекса внешнего цикла. Например: 

 for (i = 0; i < N; i++) {
     for (j = 0; j < M; j++) {
         sequence of statements
      }
  }

Внешний цикл выполняется N раз. Каждый раз, когда выполняется внешний цикл, внутренний цикл выполняется M раз. В результате операторы во внутреннем цикле выполняются в общей сложности N * M раз. Таким образом, общая сложность для двух циклов составляет O (N2).

...