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

Question

我最近发现了这个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(1)，从而将其变为O(n)？

- Adrian Jałoszewski

---

我可以使用它在不到一秒的时间内计算出第1000个元素，因此它不可能是指数级的。 - Adrian Jałoszewski

是的，随机访问引入了一个额外的因素n，但是在这里你不需要随机访问。你只需要访问前两个元素。在Haskell中，可以通过将列表与其尾部zip起来来完成这种操作。您还可以使用惰性数组而不是列表，这样可以获得O(1)的随机访问，同时保持递归公式的结构，但缺点是必须指定要获取的元素数量，因为不存在无限的数组。 - sepp2k

@Surace 这里已经有一个数据结构（列表）。这段代码不是指数级的，正如Adrian所怀疑的那样，它是二次的。 - sepp2k

Answer 1

因为Haskell中的列表查找，它是O(n^2)吗？

是的。

如果是，那么有没有办法使其像查找操作是O(1)的语言一样变成O(n)?

最简单的方法是使用惰性数组，它们具有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的第一个元素，因此0 + 1 = 1，下一个元素将是1 + 1 = 2等等。因此，这个定义确实产生了斐波那契数列。

---

¹ 尽管对于不太习惯在头脑中打递归结构的人来说，这可能会更加难以理解。

- sepp2k

Answer 2

这个程序的时间复杂度是O(n)。

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

- Emil

Answer 3

如果您使用记忆化斐波那契数列，时间复杂度应该是O(n)，因为在任何索引i处，fib(i)只计算一次。这是动态规划的美妙之处。

- Shakhawat Hossain

---

这是一个问题-在C、C++、Java等语言中，它的时间复杂度是O(n)，但在具有O(n)列表访问的语言中不是。您可以使用Java的LinkedList来获得类似的性能问题。 - Adrian Jałoszewski