Haskell中动态规划实现：该方案是否线性时空高效？

你的这个实现不具备线性时间效率，但空间效率是线性的，具体分析如下：

时间复杂度问题 #

你代码中使用了!!操作符访问列表元素，而Haskell的普通列表是单链表结构，!! k操作需要从头遍历到第k个元素，时间复杂度为O(k)。当计算第i项时，你需要获取fibs !! (i-1)和fibs !! (i-2)——这两个操作分别需要遍历i-1和i-2个元素。累加下来，计算到第n项的总时间复杂度是O(n²)，远达不到线性时间的要求。

空间复杂度分析 #

得益于Haskell的惰性求值特性，fibs作为无限列表，已经计算完成的元素会被保留在内存中（后续计算依赖这些结果，不会被垃圾回收），因此空间复杂度为O(n)，也就是线性空间。

线性时间的改进实现 #

如果想要达到线性时间的斐波那契无限列表，可以利用zipWith来避免低效的索引访问：

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

这个版本中，每个元素只会被计算一次，时间复杂度为O(n)，空间复杂度依然是O(n)（需要保留已计算的列表元素）。如果仅需计算单个斐波那契数且想优化空间到O(1)，可以使用递归函数只保留前两项的值，但这种方式无法生成无限列表。

内容的提问来源于stack exchange，提问作者kichii112