Нахождение более эффективного алгоритма

Question

У меня есть следующий псевдокод:

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

Наихудшая временная сложность этого случая должна быть O (n), поскольку назначение нового элемента для B - это просто O (1), а код запускает для l oop n раз. Это правильно?

Моя задача - найти более эффективный алгоритм, чем приведенный выше. Я имею в виду, что O (n) уже довольно быстр, поэтому я не знаю, как найти более эффективный алгоритм. У кого-нибудь есть идеи?

Заранее спасибо!

Answer 1

Если вам нужно добавить все числа от A[0] до A[i] в каждой итерации , то это O(n^2) сложность. Например, в Python:

# O(n^2) solution

a = [2, 3, 5, 7, 1, 9, 8]
b = []

for i in range(len(a)):
    sum = 0
    for j in range(i+1):
        sum += a[j]
    b.append(sum)

Чтобы сделать это O(n), вы можете рассчитать текущую сумму, используя предыдущие результаты, например:

# O(n) solution

a = [2, 3, 5, 7, 1, 9, 8]
b = [a[0]]

for i in range(1, len(a)):
    sum = b[i-1] + a[i]
    b.append(sum)

Результат будет одинаковым в обоих случаях, но вторая версия будет иметь O(n) сложность:

b
=> [2, 5, 10, 17, 18, 27, 35]

Answer 2

Алгоритм O(n) для этого будет выглядеть примерно так:

sum = 0
for i = 0 to n-1
    Add A[i] to the sum
    Store the sum in B[i].

Нет способа найти алгоритм для этой проблемы со сложностью времени выполнения менее O(n), потому что вам НУЖНО посетить все элементы в массиве, чтобы вычислить сумму всех из них. Это утверждение относится к случаю, когда у вас нет предварительных знаний о структуре массива.