Сокращение временной сложности алгоритма с помощью вложенных циклов

Question

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

Algorithm example(ArrayA, ArrayB, n)                                           
Input: 2 arrays of integers, ArrayA and ArrayB, both length n          
Output: integer

value <- 0                                                    1 operation
for i <- 0 to n-1                                             n-1 operations
    for j <- 0 to n-1                                         (n-1)^2 operations
        value <- value + (ArrayA[i] * ArrayB[j])              3(n-1)^2 operations
return value                                                  1 operation

Всего примитивных операций: n ² + 2n - 1, что дает ему временную сложность O (n ² ).

Answer 1

Применяя немного алгебры:

Итак, вот алгоритм, который вычисляет тот же результат за O (n) времени:

sum_A ← 0
for i ← 0 to n-1
    sum_A ← sum_A + ArrayA[i]

sum_B ← 0
for j ← 0 to n-1
    sum_B ← sum_B + ArrayB[j]

return sum_A * sum_B

Вообще говоря, алгоритм с вложенными циклами не всегда можно изменить, чтобы уменьшить временную сложность; но в некоторых случаях вы можете сделать это, если вы можете идентифицировать что-то определенное c относительно вычисления, что означает, что это может быть сделано другим способом.

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

Answer 2

Этот тип операции будет выполняться только через n2 раз. Причина в том, что вы должны сравнивать каждый элемент i с каждым элементом j. Например:

i*j, i*j+1,...,i*j+(n-1)
(i+1)*j, (i+1)*(j+1),...,(i+1)*(j+n-1)
.
.
.
(i+n-1)*j, (i+n-1)*(j+1),...,(i+n-1)*(j+n-1)

Просто нет способа уменьшить сложность.