Haskell 中 zipWith 斐波那契的时间复杂度

Question

在 Haskell 中，斐波那契函数的规范 zipWith 实现是：

fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

我很难分析这个的时间复杂度（fibs !!n）。试着把它写在纸上，起初我以为它是指数级的。然后 O(n^2) ，但我不知道它是如何恰好是线性的。

为什么我认为它是线性的：https://wiki.haskell.org/The_Fibonacci_sequence#Canonical_zipWith_implementation

此外，我写了另一个代码：

fibs :: [Integer]
fibs = inc (0,1) where inc (a,b) = a : inc (b,a+b)

我相信这显然是 O(n)。但是在 ghci 中使用 :set +s 选项，我发现 zipWith 实现明显优于我的。

注意：我知道添加第 n 个和第 (n-1) 个斐波那契数需要 O(n) 时间。因此，在测试时，我做了基本情况，即前两个元素 0 : 0 。使用相同的假设提到时间复杂度。

如果我能在跟踪这些函数调用方面得到一些帮助，那就太好了。我很想知道什么时候调用了哪个函数，也许打印一些东西让我知道发生了什么。

我在这方面的失败尝试：

zipWith' = trace ("Called zipWith") (zipWith)
add' a b = trace (show a ++ " + " ++ (show b)) (add a b)
fibs = trace ("Called fibs") (1 : 1 : zipWith (+) fibs (tail fibs))

这不起作用。报表只打印一个。令人惊讶的是，除了 add' 之外效果很好。

我想知道这些函数被调用了多少次以及调用的顺序。

Answer 1

我认为您的版本速度慢主要是因为您运行它没有经过优化，所以您最终构建了一堆不必要的元组。部分手动优化（和更惯用）的版本将是

fibs = inc 0 1
  where
    inc a b = a : inc b (a+b)

一起来看经典：

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

内存中的初始表示看起来很像。这是一个指向数字 1 的列表 cons 和第二个指向数字 1 的列表 cons 和一个代表 zipWith (+) fibs (tail fibs) 的 thunk。当那个 thunk 被强制时会发生什么？那么 zipWith 需要检查它的两个列表参数。它这样做，并且看到它们不为空，生成一个列表 cons 指向一个代表 1+1 的 thunk 和一个代表 zipWith (+) fibs' (tail fibs') 的 thunk，其中 fibs' 是指向 second 序列中的缺点。没有必要为每个 zipWith 参数或类似的东西再次计算 fibs。

Haskell 中 zipWith 斐波那契的时间复杂度

Time complexity of zipWith fibonacci in Haskell

time

haskell

fibonacci