單項選擇題

已知數(shù)列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)
根據(jù)遞推式寫出求數(shù)列值的遞歸算法,問原始算法與采用函數(shù)值緩存的算法時間復雜度分別為多少?()

A.O(n4);O(n2
B.O(5n);O(1)
C.O(4n);O(n)
D.O(5n);O(n2


您可能感興趣的試卷

你可能感興趣的試題

2.單項選擇題下列哪個算法使用到了分治策略?()

A.迷宮尋路
B.博物館大盜問題
C.二分查找
D.單詞最短編輯距離

3.多項選擇題以下哪些問題不適合用遞歸算法求解?()

A.圖像、語義識別
B.查找有序列表中某元素是否存在
C.計算兩個數(shù)的差
D.求斐波那契數(shù)列第N項的值