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

Question

Является ли временной сложностью следующий код O (NV^2)?

for i from 1 to N: 
    for j from 1 to V: 
     for k from 1 to A[i]://max(A) = V 
      z = z + k 

Answer 1

да, когда мы говорим о O-notation, мы всегда думаем о верхнем переплете (или в худшем случае).

Таким образом, сложность для этого кода будет равна

O(N*V*maximum_value_of_A) 
=O(N*V*V) // since,maximum value of A=V,so third loop can maximally iterate from 1 to V---V times 
=O(N*V^2). 

Answer 2

Достоверно O (NV^2), поскольку это означает, что код никогда не медленнее, чем это. Поскольку max (A) = V, вы можете сказать, что наихудший случай был бы тогда, когда в каждом индексе A есть V. Если это так, то сложность может быть ограничена O (NV * V).

Вы можете очень точно рассчитать, что сложность цикла for k может быть O (avg (A)). Это позволяет нам сказать, что вся функция Omega (NV * Avg (A)), где ср (А) = < В.

Theta обозначения (что означает asympthotical сложность) бы можно сказать, как Theta (NV * O (V)), O (V), представляющий сложность функции, которая никогда не будет расти быстрее, чем V, но не является постоянной.