寻找更有效的算法

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），并且代码将for循环运行n次。正确吗？

我的任务是找到一种比上述算法更有效的算法。我的意思是O（n）已经相当快了，所以我不知道如何找到更有效的算法。有人有什么想法吗？

提前感谢！

Answer 1

O(n)算法将类似于：

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