Какова временная сложность данного фрагмента?

Question

for i = 1 to n do 
    for j = 1 to i do 
     for k = 1 to j do 

Какова его временная сложность с точки зрения «n»?

Answer 1

Внутренняя петля, очевидно, будет работать j раз. Если предположить, что он содержит операции на сумму 1 единицу времени, то это будет:

T_inner(j) = j 

Средний цикл будет выполняться i раз, то есть

T_middle(i) = Sum {j from 1 to i} T_inner(j) 
      = Sum {j from 1 to i} j 
      = i/2 * (1 + i) 

Наконец:

T_outer(n) = Sum {i from 1 to n} T_middle(i) 
      = Sum {i from 1 to n} (i/2 * (1 + i)) 
      = 1/6 * n * (1 + n) * (2 + n) 
      = 1/6 n^3 + 1/2 n^2 + 1/3 n 

И это, очевидно, O(n^3).

Примечание: Учитываются только операции во внутреннем большинстве блоков. Он пренебрегает операциями, необходимыми для выполнения цикла. Но если вы включите их, вы увидите, что временная сложность одинакова.