haskell - Haskell 中的整数时间复杂度

Question

上周我在学校完成了一项作业，以实现计算斐波那契数列中第 n 个数字的函数。 “子分配”是使用累积(可能不是正确的翻译)来实现它，以便给函数 O(n) 时间复杂度。这一切都很好，直到我尝试制作函数(Int -> Integer)。通过一些实验，我意识到对于非常大的数字，时间复杂度接近 O(n^2)。
我突然想到这一定是因为 Integer 实现，这让我有点好奇它是如何工作的。我做了一些谷歌搜索，没有找到任何似乎有用的东西，所以我转向你们，希望得到一个解释或一个彻底解释它的链接。

我的代码:

ackfib 0 = 0
ackfib 1 = 1        
ackfib n = loop n 1 0 1
    where
        loop n n1 n2 i 
            | i < n     = loop n (n1+n2) n1 (i+1)
            | i == n    = n1
            | i > n     = error "n must be greater than or equal to 0"

我很感谢所有的答案

维克多

Answer 1

这实际上与 Haskell 无关，这只是斐波那契数以指数级快速增长这一事实的结果。具体来说，第 n 个斐波那契数大约有 (log2 φ) n 或大约 0.48 n 位，其中 φ 是黄金比例 (1 + sqrt 5)/2。由于添加 k 位整数需要 O(k) 时间，因此您的 O( n) 添加实际上总共需要 O(n^2) 时间，因为平均而言，您添加的数字有 O(n) 位。

(坚持者的注意事项:上面的大 O 应该是大 Theta。)