创建具有更好运行时间的算法

Question

我有一个包含数字 A[1],A[2]...,A[n] 的矩阵 A 和一个矩阵 B (nxn)，我想保存所有可能的和。计算 B 矩阵的简单算法是：

for i=1,2,...,n
    for j=i+1,i+2,...,n
        add the number from A[i] to A[j]
        save the results to B[i][j]
    endfor
endfor

我想把这个算法改得更好（有更好的运行时间）。我将 i=1,2,...n 的第一个更改为 i=1，并在第二个的末尾增加了它。我还认为我做了更多计算，即 needed.To 计算 B[1][5] 我必须计算 A[1][2]+A[1][3]+A[1][4] 但是这个和也在 B[1][4] 中。所以我也可以用更少的计算来计算这个（B[1][4]+A[1][5]）。谁能帮我改进这个算法？

Answer 1

for i=1,2,...,n
    for j=i,i+1,i+2,...,n
        if i == j then B[i][j] = A[j]
        else B[i][j] = B[i][j - 1] + A[j]
    endfor
endfor

创建具有更好运行时间的算法

Creating an algorithm with better runtime

algorithm

pseudocode

time-complexity