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

运行时间应该是O（n），这是我想出来的，是正确的吗？谢谢给定数组A [1..n]作为输入，填入第二个数组B [1..n]，使得B [i] = A [1] + ... + A [i]

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]

来源

2012-07-21 Hassan Ghorbani

为什么不把它转换成你喜欢的语言，编译它，看它是否给出了正确的结果？ – 2012-07-21 11:09:59

好主意Oli，但是我正在学习考试，我不能在测试中编译，我用第一个来读取值...但它说它应该有运行时间O（n ）在任务 – 2012-07-21 11:14:59

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

你手头有问题正是这个属性：以B[n]的解决方案可以在O(1)构造，如果给你一个解决方案，B[n-1]，那就是你的算法做了什么，为O(N)运行时间。这样的解决方案在实践中非常有用：我曾经使用过像你这样的算法来加速我的程序中的一段启动代码，从几分钟到几秒钟（它正在添加向量，所以它从O(3)到O(2)）。

来源

2012-07-21 11:16:59 dasblinkenlight

非常感谢你dasblinkenlight – 2012-07-21 11:24:22

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

回答

相关问题