From: Mathieu Bouchard <matju@...>
Date: 2002-02-10T00:52:38+09:00
Subject: Re: Reg: tiny contest: who's faster? (add_a_gram)


On Sun, 10 Feb 2002, Niklas Frykholm wrote:
> For example, calculating the fibonnaci function.
> Without dynamic programming:
> With dynamic programming
> Now compare the running times of f1(100) and f2(100) ;)

f1(100) is run f1(1) times
f1(99) is run  f1(2) times
...
f1(1) is run  f1(98) times
f1(0) is run  f1(99) times

and sum of f1 for n in 0..99 is f1(101) (a special property of fibonacci's
function)

fibonacci is asymptotically an exponential (where the golden mean is the
base: 1.618**n)

the one using dynamic programming takes n time for small n; for large n,
you have to take number size into account, and then it's n**2; it's still
much better than exponential time =)

Simple functions, like fibonacci's, are easy to rewrite in iterative forms
that don't even need a cache (e.g. this one can be run in n memory-size
instead of n**2); more complex ones may make a cache much worthwhile.

________________________________________________________________
Mathieu Bouchard                   http://hostname.2y.net/~matju