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

Question

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

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

Это O (n ^ 2)?

Answer 1

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

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

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

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

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

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

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 спрашивает, существует ли константа, которую мы можем применить к одной функции, чтобы она была больше другой, для достаточно большого ввода (см. Страницу википедии)

Answer 2

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

если и 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)

Answer 3

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

Answer 4

Давайте проследим, сколько раз каждый цикл выполняется на каждой итерации.

      for (int i = 1; i <= n; i++){  // outer loop
    for (int j = 1; j <= i; j++){  // inner loop
        // some code
    }
}

В первой итерации внешнего цикла (i = 1) выполняется внутренний цикл once.

Во второй итерации внешнего цикла (i = 2) выполняется внутренний цикл twice.

На третьей итерации внешнего цикла (i = 3) выполняется внутренний цикл thrice.

Итак, на последней итерации внешнего цикла (i = n) выполняется внутренний цикл n times.

Таким образом, общее количество выполнений этого кода равно

1 + 2 + 3 + … + n

= (n(n + 1) / 2)(Формула суммы натуральных чисел)

= (((n^2) + n) / 2)

= O(n^2)

Answer 5

На 1-й итерации внешнего цикла (i = 1) внутренний цикл будет повторяться 1 раз. На 2-й итерации внешнего цикла (i = 2) внутренний цикл будет повторяться 2 раза. На 3-й итерации внешнего цикла. (i = 3), внутренний цикл будет повторяться 3 раза
,
,
На ЗАКЛЮЧИТЕЛЬНОЙ итерации внешнего цикла (i = n) внутренний цикл будет повторяться n раз

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

((n)*n) / 2 = (n^2)/2 = O(n^2) times 

Answer 6

Да, временная сложность этого составляет O(n^2).

Answer 7

Как показали другие правильные ответы, результирующая сложность составляет O(n²). В первую очередь это O(n²/2), что сводится к O(n²). Вот почему /2 не имеет значения:

Важно понимать, что временная сложность относится не к скорости алгоритма, а к скорости изменения скорости относительно n. Скорость изменения.

Предположим, у нас есть два алгоритма:

• A со сложностью O (n²)
• B со сложностью O(n²/2)

Для размера ввода (n), равного 5, вы можете решить временную сложность следующим образом:

• Для A - O(n²), что равно 25
• Для B - O(n²/2), что равно 12,5.

Теперь для ввода размера 10 вы разрешите сложность, например:

• Для A - O(n²), что равно 100
• Для B - O(n²/2), что равно 50

В любом случае удвоение размера входных данных увеличило время выполнения в четыре раза. Это означает, что с точки зрения временной сложности O(n²/2) совпадает с O(n²). Как я уже сказал, временная сложность — это не мера того, сколько времени требуется для запуска алгоритма, а то, как это время изменяется в зависимости от размера входных данных.

Answer 8

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

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

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

Answer 9

Я думаю, что проще всего думать об этом так:

Внешний цикл выполняется n раз, и, по крайней мере, для n / 2 из этих итераций внутренний цикл выполняется не менее n / 2 раз. Поэтому общее число итераций внутреннего цикла составляет по меньшей мере п ²/4. Это O(n²)

Точно так же внешний цикл выполняется n раз, а на каждой итерации внутренний цикл выполняется не более n раз. Таким образом, общее количество итераций внутреннего цикла не превышает n ² . Это тоже в O (n ²).

Answer 10

Внутренний цикл зависит от внешних циклов, а внутренний цикл выполняется 1 раз, что дает мне

для n = 5, если i = 1, внутренний цикл выполняется 1 раз 1 = 1

если i = 2 внутренние петли выполняются 2 раза 1 + 2 = 3

если i = 3 внутренние петли выполняются 3 раза 1 + 2 + 3 = 6

если i = 4 внутренние петли выполняются 4 раза 1 + 2 + 3 + 4 = 10

если i = 5, внутренние петли выполняются 5 раз 1 + 2 + 3 + 4 + 5 = 15

Сверху мы можем знать, что n (n + 1) / 2

Итак, O(n *(n + 1)) / 2 = O(n2 / 2 + n / 2) = O(n2 / 2) + O(n / 2)

Я не очень разбираюсь в алгоритмах анализа, поэтому не стесняйтесь исправлять мой ответ.