已知数列G(x)满足:G(1)=G(2)=G(3)=G(4)=1G(x)=G(x-1)+G(x-2)+G(x-3)+G(x-4)(x≥5)根据递推式写出求数列值的递归算法,问原始算法与采用函数值缓存的算法时间复杂度分别为多少?


已知数列G(x)满足:G(1)=G(2)=G(3)=G(4)=1G(x)=G(x-1)+G(x-2)+G(x-3)+G(x-4)(x≥5)根据递推式写出求数列值的递归算法,问原始算法与采用函数值缓存的算法时间复杂度分别为多少?

A.O(4^n);O(n)

B.O(5^n);O(n^2)

C.O(n^4);O(n^2)

D.O(5^n);O(1)

正确答案:O(4^n);O(n)


Tag:算法与数据结构 算法 数列 时间:2022-01-19 14:01:43