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

Question

Извините, если этот вопрос является дубликатом, или вроде глупо, но я действительно новый алгоритму развития) Можете ли вы объяснить мне, что сложность следующего фрагмента кода

for (int i=0; i<n; i++) { 
    for (int j=0; j<i; j++) { 
     do stuff... 
    } 
} 

является сложность этого кода n^2 или nlogn? Thanks

Answer 1

Сложность O(n^2).

Для первой итерации внешнего цикла, внутренний цикл будет повторять 0 раз

Для второй итерации внешнего цикла, внутренний цикл будет повторять 1 раз.

Для третьей итерации внешней петли внутренний цикл будет итерировать 2 раз.

.........

Для n-й итерации внешнего цикла, внутренний цикл будет повторять n - 1 раз.

Общее число итераций = 0 + 1 + 2 + 3 + 4 ...... + (n - 1)

Мы знаем, сумма арифметических рядов

1 + 2 + 3 + ..... + (n - 2) + (n - 1) + n = (n * (n + 1))/2 

Так,

0 + 1 + 2 + 3 + 4 ...... + (n - 1) 
= (n * (n - 1))/2 
~ n^2 

Рассматривая do stuff фаза будет выполняться в постоянном времени, общее временная сложность O(n^2).