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

Question

Я пытаюсь решить этот алгоритм, но я не уверен, что вот код (пытаясь понять сложность)

For (i =0, i<N, i++) {  
    For (j=0, j<i/2, j++)  {   
        S.O.P (“”);  
    } 
}

SOP обозначает инструкции, данные ЦПУ.

Answer 1

Я не знаю, что означает SOP, но ради вопроса, я предполагаю, что это занимает фиксированное время - O (1).

Следовательно, осталось только одноопределяет время, которое требуется циклам for.

for (i =0, i<N, i++) {         // n times 
    For (j=0, j<i/2, j++)  {   // for each time, this runs n/2 times
        S.O.P (“”);            // fixed time O(1)
    } 
}

Учитывая это, мы можем вычислить:

T(n) = {sum for i from 0 to n} i/2 = (1/2)*(n*(n-1)/2)
T(n) = (n*(n - 1)/4) * O(1) = O(n^2/4) = O(n^2)

Таким образом, окончательная сложность времени будет O(n^2) (On в квадрате).