запутался во временной сложности следующего веселья c. Хорошее объяснение было бы полезно

Question

Если первый l oop работает n + 1 раз. секунда l oop работает n (n + 1) раз. третий л oop будет баллотироваться на ??? у него n ^ 2 + 1 одно отношение со вторым l oop я думаю, но как насчет первого

somefunction(n) {  
 c = 0      
 for (i = 1 to n*n)          
   for (j = 1 to n)               
     for (k = 1 to 2*j)                    
        c = c+1     
  return c 
}

Answer 1

Первый l oop имеет O(n**2) итераций.

Второй l oop имеет O(n) итераций.

Третий l oop имеет O(n) итераций также, поскольку j неуклонно растет к n.

(Немного легче увидеть, если вы суммируете, сколько раз c = c + 1 выполняется для двух внутренних циклов вместе. Внутренний l oop выполняется 2 раза для j = 1, 4 для j = 2, ... и 2*n раз для j = n. 2 + 4 + .. + 2 * n = O (n ** 2).)

Затем можно (свободно говоря) умножить три значения вместе, чтобы получить общую оценку O (n ** 4).