Временная сложность алгоритма суммирования префиксов

Question

Учитывая следующий псевдокод, мне интересно, правильный ли мой мыслительный процесс при попытке определить сложность времени.

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

Алгоритм будет зацикливаться n раз, и, поскольку последняя итерация потребует наибольшего количества вычислений (n вычислений), алгоритм в общей сложности составит n^2 + f(n) вычисления. где f(n) полином степени n^2 или менее. Поэтому этот алгоритм является квадратичным O(n^2),

Answer 1

Как сложность времени Add the numbers A[0] thru A[i]. является \Theta(i), временная сложность вашего кода будет \Theta(1 + 2 + 3 + ... + \Theta(n)) = \Theta(n^2), Следовательно, ваш анализ вашего кода верен.

Answer 2

Мы можем заменить ваш код следующим кодом

    for i 0 to n - 1
        for j 0 to i
            b[i] += a[j]   <---

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

просто для простоты допустим, что все элементы a[i] равны 1, поэтому, если мы находим сумму b[i], когда i равно 0 - n -1, то мы находим число раз, когда была выполнена 3-я строка.

i: b[i]
0: 1
1: 2
2: 3
..
n - 1: n

поэтому общая сумма всех B[i] равна n * (n + 1) / 2, что равно O(n^2)