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

Ответ 1

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

Обычно (но не всегда) одна петля, вложенная в другую, вызывает O (n²).

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

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

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

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

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

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

От веб-сайта: 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)

Ответ 2

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

если оба я и 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)

Ответ 3

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

Ответ 4

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

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

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

Ответ 5

На 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