16 Jun
2005
16 Jun
'05
5:18 a.m.
Radu Grigore wrote:
Anyway, I was wondering if the O(n) space and O(n^2) time solution can be implemented in Haskell. Another way to ask this. Consider the classic fibonacci example. Can one compute the n-th fibonacci number in O(n) time and O(1) space, i.e. remember only the "last" two values during computation?
Assuming an O(1) + operation you can do fib n = f n 1 1 where f 0 _ b = b f n a b = f (n-1) (a+b) a List based solutions should also work if garbage collection is done right, e.g., fib n = fs !! n where fs = 1 : 1 : zipWith (+) fs (tail fs) -- Lennart