Почему сложность O (n)?

Question

Это программа, используемая для поиска наибольшей суммы смежных подмассивов в одномерном массиве чисел.

int maxSubArraySum(int a[], int size) 
{ 
   int max_so_far = 0, max_ending_here = 0; 
   for (int i = 0; i < size; i++) 
   { 
       max_ending_here = max_ending_here + a[i]; 
       if (max_ending_here < 0) 
           max_ending_here = 0; 

       /* Do not compare for all elements. Compare only    
          when  max_ending_here > 0 */
       else if (max_so_far < max_ending_here) 
           max_so_far = max_ending_here; 
   } 
   return max_so_far; 
} 

Мой вопрос: как нам найти сложность этого кода?

Answer 1

Сложность O (n), потому что мы не учитываем каждую деталь по одному (операторы присваивания, Subtractions et c) и добавляем ее к сложности, как я думал. Мы скорее считаем операции очень общими. В этом случае l oop - это наша сложность. L oop происходит n раз (где n - количество элементов в нашем массиве), таким образом -> O (n) сложность , Операции, не относящиеся к l oop, мелкие детали, как я уже сказал, -> O (1) сложность

И поэтому T (n) = O (1) + O (n) = O (n ).

Answer 2

Учитывая 'n' размерность вашего входного размера, в вашем случае временная сложность составляет O (n ^ 2), так как вы итерируете размер n раз с циклом for. Другие операции выполняются за постоянное время O (n), по этой причине они являются прослеживаемыми для всей сложности времени.