运行时间应该是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]
运行时间应该是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]
是的,这是正确的。您的解决方案是最简单的案例dynamic programming,这是一种大大加快解决方案算法的技术,可以从较小的子问题的解决方案构建解决方案。
你手头有问题正是这个属性:以B[n]
的解决方案可以在O(1)
构造,如果给你一个解决方案,B[n-1]
,那就是你的算法做了什么,为O(N)
运行时间。这样的解决方案在实践中非常有用:我曾经使用过像你这样的算法来加速我的程序中的一段启动代码,从几分钟到几秒钟(它正在添加向量,所以它从O(3)
到O(2)
)。
非常感谢你dasblinkenlight – 2012-07-21 11:24:22
为什么不把它转换成你喜欢的语言,编译它,看它是否给出了正确的结果? – 2012-07-21 11:09:59
好主意Oli,但是我正在学习考试,我不能在测试中编译,我用第一个来读取值...但它说它应该有运行时间O(n )在任务 – 2012-07-21 11:14:59