как найти временную сложность, используя значение шага

Question

sum(array,n) 
{ 
    tsum=0; 
    for(i=0;i<n;i++) 
    tsum=tsum+array[i]; 
    return tsum; 
} 

Answer 1

В терминах big-O, это линейная пропорционально количеству элементов массива обработанных, так что O (N)

(Примечание, код перезаписывает параметр я , предположим, что параметр должен был быть n, чтобы указать количество элементов массива для суммирования?)

Answer 2

Вы объявляете tsum = 0 за 1 шаг, тогда вы запускаете цикл для n шагов. на каждой итерации вы делаете сумму, которая составляет 1 шаг, а затем вы возвращаете tsum за 1 шаг. Ваш счетчик шагов составляет приблизительно:

1 + 3n + 1, что является O (n) в терминах большого числа обозначений, которое игнорирует константы и все члены младшего порядка (если их постоянное число).) Есть 3n шагов, как и в каждой итерации, вы увеличиваете переменную i, проверяете, меньше ли она n, а затем введите цикл, чтобы выполнить вычисление.

Answer 3

       Cost   Times 
tsum=0;       c1    1 
for(i=0;i<n;i++)    c2    n+1 
    tsum=tsum+array[i];   c3    n 
return tsum;     c4    1 

Общая стоимость алгоритма является 1 * С1 + (п + 1) с2 + п с3 + с4 1 *

Таким образом, время, необходимое для этого алгоритма пропорциональна п.