记忆斐波那契的时间复杂度

我最近遇到了这个 Haskell 记忆斐波那契实现：

fibonacci :: Int -> Integer
fibonacci = (map fib [0 ..] !!)
  where fib 0 = 0
        fib 1 = 1
        fib n = fibonacci (n - 1) + fibonacci (n - 2)

我想知道第一次生成第 n 个斐波那契数的时间复杂度。是因为 Haskell 中的列表查找而导致 O(n^2) 吗？如果是，那么有没有办法以某种方式使其成为 O(n)，就像查找操作为 O(1) 的语言一样？

是因为 Haskell 中的列表查找而导致 O(n^2) 吗？

Yes.

如果是，那么有没有办法以某种方式使其成为 O(n)，就像查找操作为 O(1) 的语言一样？

最简单的方法是使用惰性数组，它具有 O(1) 随机访问。这意味着，您必须指定数组大小，这样您就不再具有无限序列，但在其他语言中也有相同的限制。例如，您可以使用这样的方法Data.Vector:

import Data.Vector

fibsUpto100 :: Vector Integer
fibsUpto100 = generate 100 fib
    where fib 0 = 0
          fib 1 = 1
          fib n = fibsUpto100 ! (n-1) + fibsUpto100 ! (n-2)

由于惰性，在计算向量的元素之前不会计算任何内容，此时向量的所有先前元素（之前尚未计算过）也将被计算。一旦计算完毕，每个值都会存储在向量中，因此不会对任何值进行多次计算。

当然，如果有无限的数字列表就更好了。实现此目的的一种方法是将计算第 n 个斐波那契数的标准 O(n) 方法（使用跟踪当前和前一个元素的 while 循环）转换为递归 Haskell 函数，然后调整该函数以将每个元素存储在一个列表。

while 循环的基本翻译是：

fib 0 = 0
fib n = fibHelper n 0 1
  where
    fibHelper 0 _ current = current
    fibHelper n previous current =
        fibHelper (n-1) current (current + previous)

调整它以保留列表，我们得到：

fibs = 0 : genFibs 0 1
  where
    genFibs previous current =
        current : genFibs current (current + previous)

另一种更简洁的方法是使用自己的尾部来定义列表。也就是说，我们希望列表中的每个元素都是前一个元素+之前的元素，我们通过获取列表及其尾部，将它们添加在一起并将结果反馈到列表中来实现这一点。这导致以下定义：

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

这里 0 和 1 分别是第一个和第二个元素，然后剩余的元素在由zipWith (+) fibs (tail fibs)。该列表的第一个元素（即整个列表的第三个元素）将是fibs+ 第一个元素tail fibs, so 0 + 1 = 1，下一个元素是1 + 1 = 2等等。所以这个定义实际上产生了斐波那契数列。

1 尽管对于不太习惯在头脑中打递归结的人来说可能不太容易理解。