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

Question

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

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

ли это O (N^2)?

Answer 1

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

Answer 2

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

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

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

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

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

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

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

---

4г позже Edit: Поскольку этот пост, кажется, чтобы получить достаточное количество трафика. Я хочу более подробно объяснить, как мы связали выполнение с 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)

Answer 3

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

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

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

Answer 4

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

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

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

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

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