在我正在学习的函数式编程课程的当前练习任务中,我们必须制作给定函数的记忆化版本。为了解释记忆化,下面给出一个示例:
我不完全理解这个如何工作。
我们来叫
fiblist = [ fibm x | x <- [0..]]
fibm 0 = 0
fibm 1 = 1
fibm n = fiblist !! (n-1) + fiblist !! (n-2)
我不完全理解这个如何工作。
我们来叫
fibm 3
。fibm 3
--> fiblist !! 2 + fibList 1
--> [fibm 0, fibm 1, fibm 2] !! 2 + [fibm 0, fibm 1] !! 1
--> fibm 2 + fibm 1
--> (fiblist !! 1 + fiblist 0) + 1
--> ([fibm 0, fibm 1] !! 1 + [fibm 0] !! 0) + 1
--> (fibm 1 + fibm 0) + 1
--> 1 + 0 + 1
--> 2
从其他问题/答案和谷歌搜索中,我了解到评估的fiblist在调用之间是共享的。
这是否意味着,例如对于fiblist !! 2 + fiblist !! 1
,列表值仅针对fiblist !! 2
计算一次,然后只是为了fiblist !! 1
重复使用?
然后,每次调用仅计算两个斐波那契数,因此没有指数数量的调用。但是,在fiblist
函数的“较低”级别中怎样从原始fibm
调用中计算出的fiblist
受益?
if (f x) > 0 then f x else 0
,其中f x
是某个昂贵的函数调用。如果if条件为真,那么f x
将被重复计算吗,还是值将被简单地重用? - user42179fiblist !! n
的时间复杂度也是O(n)
,我相信第一次计算fibm n
会对每个i < n
的fiblist !! i
进行评估,这样的时间复杂度是O(n^2)
。你可以做得更好... - Itai Zukerman