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

Question

我最近遇到了这个Haskell的memoized fibonacci实现:

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)的语言一样？

Answer 1

\n

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

\n

\n\n

是的。

\n\n

\n

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

\n

\n\n

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

\n\n

import Data.Vector\n\nfibsUpto100 :: Vector Integer\nfibsUpto100 = generate 100 fib\n    where fib 0 = 0\n          fib 1 = 1\n          fib n = fibsUpto100 ! (n-1) + fibsUpto100 ! (n-2)\n

\n\n

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

\n\n

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

\n\n

while 循环的基本翻译是：

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

这里 0 和 1 分别是第一个和第二个元素，其余元素位于 生成的列表中zipWith (+) fibs (tail fibs)。该列表的第一个元素（即整个列表的第三个元素）将是 + 的第一个元素fibs+ 的第一个元素tail fibs，因此0 + 1 = 1，下一个元素将是1 + 1 = 2，依此类推。所以这个定义实际上产生了斐波那契数列。

\n\n\n\n

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

\n