时间memoized斐波纳契

的复杂最近，我遇到了这个哈斯克尔memoized实施斐波纳契：时间memoized斐波纳契

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

来源

2017-03-13 Adrian Jałoszewski

我可以在一秒钟内使用它来计算第1000个元素，所以它不能是指数。 –

是的，随机访问引入了一个额外的因子n，但这里不需要随机访问。你只需要访问前两个元素。在Haskell中，这种事情可以通过拖拽一个列表来完成。你也可以使用懒惰数组而不是列表，它给你O（1）随机访问，同时保留递归公式的结构，缺点是你必须指定你想要的元素的数量，因为没有无限的东西阵列。 – sepp2k

@Surace这里已经有一个数据结构（列表）。这个代码并不是指数函数，而是阿德里安怀疑的二次函数。 – sepp2k

它是为O（n^2），因为在Haskell列表中查找的？

是的。

如果是，那么有没有办法以某种方式使它O（n）像查找操作是O（1）的语言一样？

最简单的方法是使用惰性数组，它具有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)

另一个更concise¹的方式来达到同样的事情会使用自己的尾巴来定义列表。那就是我们希望列表中的每个元素都是前一个元素+之前的元素，我们通过获取列表和尾部来实现这一点，将它们相加并将结果反馈到列表中。这导致了以下定义：

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

这里0和1分别是第一和第二元件，然后将剩余的元件在由zipWith (+) fibs (tail fibs)产生的列表。该列表的第一个元素（即整个列表的第三个元素）将是fibs的第一个元素+第一个元素tail fibs，因此0 + 1 = 1，下一个元素将是1 + 1 = 2等等。所以这个定义实际上产生了斐波那契数列。

¹虽然可能不太理解人们不太习惯于在他们的头上绑定递归结。

来源

2017-03-13 12:18:23 sepp2k

-3

如果您使用memoized斐波那契时间复杂度应为O(n).，因为在任何指数我fib(i)只计算一次。这是一个动态编程的美丽。

来源

2017-03-13 05:55:32

这是一个问题 - 在C，C++，Java等语言中将会是O（n），但在O（n）列表访问的语言中不会。你可以通过使用Java LinkedList来获得类似的性能问题。 –

这运行在O（n）时间。

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

来源

2017-03-13 08:01:58 Emil

可能值得简要解释它是如何工作的。 – Alec

时间memoized斐波纳契

回答

相关问题