Temporal difficulty memoized fibonacci

Question

I recently came across this Fibonacci implementation written in Haskell's memory:

fibonacci :: Int -> Integer fibonacci = (map fib [0 ..] !!) where fib 0 = 0 fib 1 = 1 fib n = fibonacci (n - 1) + fibonacci (n - 2) 

I'm curious about the time complexity for generating the nth Fibonacci number for the first time. Is it O (n ^ 2) due to list search in Haskell? If so, is there a way to somehow make it O (n) look like languages ​​where the search operation is O (1)?

Answer 1

Is it O (n ^ 2) due to list search in Haskell?

Yes.

If so, is there a way to somehow make it O (n) look like languages ​​where the search operation is O (1)?

The easiest way is to use lazy arrays that have O (1) random access. This means that you need to specify the size of the array, so you no longer have an infinite sequence, but you have the same restriction in other languages. For example, you can do it like this using 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) 

Because of laziness, nothing will be calculated until the element of the vector is evaluated, after which all previous elements of the vector (which have not been evaluated earlier) will also be evaluated. After evaluation, each value is stored in a vector, so nothing is evaluated more than once.

Of course, it would be better to have an endless list of numbers. One way to achieve this is to translate the standard O (n) way of calculating the nth Fibonacci number (using the while loop, which keeps track of the current and previous item), with the Haskell recursive function, and then adjusts this to store each item in the list.

Basic translation of the while loop:

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

Adjusting this to save the list, we get:

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

Another, more concise way to achieve the same would be to define a list using your own tail. That is, we want each element of the list to be the previous element + element before that, and we implement it by taking the list and its tail, adding them together and feeding the result back to the list. This leads to the following definition:

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

Here 0 and 1 are the first and second elements, respectively, and then the remaining elements are in the list created by zipWith (+) fibs (tail fibs) . The first element of this list (i.e. the third element of the entire list) will be the first element fibs + of the first element tail fibs , so 0 + 1 = 1 next element will be 1 + 1 = 2 and so on. Therefore, this definition does generate a Fibonacci sequence.

---

¹ Although, perhaps, it is less clear to people who are not too used to linking recursive nodes in their heads.

Answer 2

This runs in O (n) time.

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

Answer 3

if you are using memoized fibonacci, the time complexity should be O(n). , because in any index i fib(i) calculated only once. this is the beauty of dynamic programming.