相关疑难解决方法(0)

我最近遇到了这个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)的语言一样？

这是非常简单的Haskell代码,用于查找满足毕达哥拉斯定理的1到200的所有毕达哥拉斯整数X ^ 2 = Y ^ 2 + Z ^ 2

哈斯克尔:

let l = [1..200]
let pythagoras = [ x | x <- l, y <- l, z <- l, x^2 == y^2 + z^2]

完成它需要24.1秒,

Swift:使用标准循环 0.05秒

C:使用标准循环 0.022秒