The highly inefficient fibonacci algorithm is still quite interesting.
When computing fib(n), for k less than n fib(k) is called fib(n-k) times, except when k is 0. This is called n-2 times. The total number of calls for fib(n) is
[sum (for k less than n) fib(k)]+fib(n-2)
Quick python script to check:
d={}
def fib(n):
if d.has_key(n):
d[n]=d[n]+1
else:
d[n]=1
if n==0: return 1
if n==1: return 1
return fib(n-1)+fib(n-2)
On building an integrated QuantLib/Lua platform on the world's most popular computer.
Friday, March 19, 2010
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment