arrays - 给定一个数组 A[1..n] 作为输入，填写第二个数组 B[1..n] 使得 B[i] = A[1] + ... + A[i]

Question

运行时间应该是O(n)，这是我想出来的，对吗？谢谢

for (i = 1 ; i < A[n]; i++)
  A[i] = 0

B[i] = 0;
for i in A[1..n]
  B[i] = B[i] + A[i]

Answer 1

是的，这是正确的。您的解决方案是最简单的动态编程案例，这是一种可以大大加快解决方案算法的技术，该解决方案可以从较小的子问题的解决方案中构建。

您手头的问题恰好具有此属性：如果您得到 的解决方案，B[n]则可以构造的解决方案，这就是您的算法所做的，运行时间为。O(1)B[n-1]O(N)

这样的解决方案在实践中非常有帮助：我曾经使用像你这样的算法来将我的程序中的一段启动代码从几分钟加速到几秒钟（它是添加向量，所以它从O(3)到O(2)）。