Какова сложность этого алгоритма? BiGo

Question

У меня есть следующий алгоритм:

for (i=0; i<=n-1; i++) { 
    for (j=i; j<=n-1; j++) { 
     sum = 0; 
     for (k=i; k<=j; k++) { 
      sum = sum + v[k]; 
     if (sum > max) max = sum; 
     } 
    } 
} 

Сложность первой является О (п), во-вторых, п-я, третий J-+ 1.

Я знаю, что O (n^3) является верхней границей. Но какова истинная вещь, которую мы можем считать сложностью этого алгоритма? Это O (n^3)?

спасибо.

Answer 1

Это O(n^3) в худшем случае (если i, j и k имеют одинаковую стоимость). Это в лучшем случае O(n), когда j и k равны 0 или 1 :)

Поскольку вы должны быть готовы к худшим данным случае (и это является основной причиной экзаменационной сложности), вы должны взять на себя O(n^3)

Answer 2

Я думаю, что O (n^3), пределы итераций не имеют значения.