单项选择题
已知数列G(x)满足:
G(1)=G(2)=G(3)=G(4)=1
G(x)=G(x-1)+G(x-2)+G(x-3)+G(x-4)(x≥5)
根据递推式写出求数列值的递归算法,问原始算法与采用函数值缓存的算法时间复杂度分别为多少?()
A.O(n4);O(n2)
B.O(5n);O(1)
C.O(4n);O(n)
D.O(5n);O(n2)
点击查看答案&解析

单项选择题
已知数列G(x)满足:
G(1)=G(2)=G(3)=G(4)=1
G(x)=G(x-1)+G(x-2)+G(x-3)+G(x-4)(x≥5)
根据递推式写出求数列值的递归算法,问原始算法与采用函数值缓存的算法时间复杂度分别为多少?()
A.O(n4);O(n2)
B.O(5n);O(1)
C.O(4n);O(n)
D.O(5n);O(n2)
微信扫一扫,加关注免费搜题