Как рассчитать временную сложность этого базового c алгоритма суммирования?

Question

Я хочу понять, что и как рассчитать временную сложность этого алгоритма, приведенного в псевдокоде ниже. Я подозреваю, что T. C - это O (n), так как все oop выполняет итерацию по всему списку, но я не уверен, или это O (n ^ 2), поскольку в каждом l oop search функция списков также называется? Но также в целом, как рассчитать временные сложности данных алгоритмов. Заранее спасибо.

for i = 0 to n-1
    Add the numbers A[0] thru A[i]
    Store the result in B[i]

Answer 1

Время работы вашего алгоритма O (n ^ 2). Во второй строке вы суммируете A [0] в A [i]. Таким образом, l oop повторяется n раз. В первой итерации вы добавляете A [0], затем A [0] + A [1], затем A [0] + A [1] + A [2] и т. Д.

Итак, в Вообще, на итерации я добавляю числа Таким образом, время выполнения будет:

1 + 2 + 3 + ... + n

Это сумма первых n чисел, которая оценивается как n(n+1)/2: https://brilliant.org/wiki/sum-of-n-n2-or-n3/

В общем, не каждая строка внутри al oop имеет постоянное время. Попробуйте взглянуть на то, что происходит для каждой строки на нескольких разных итерациях l oop, чтобы понять, что происходит. Если он изменяется на каждой итерации, то он не является постоянным.

Однако существует алгоритм O (n), в котором вы просто увеличиваете переменную суммы:

sum = 0
for i = 0 to n - 1:
    sum += A[i]
    B[i] = sum

В этом случае на начало итерации i, sum уже хранит сумму от A [0] до A [i-1], поэтому, чтобы получить сумму от A [0] до A [i], просто добавьте A [i]