L2
APS1070 Fall 2021¶
Lecture 2¶
Slow and Fast Algorithms for the Fibonacci Sequence
In [ ]:
# SLOWFIB
def slowfib(n):
if n<0:
return(0)
elif n==0:
return(0)
elif n==1:
return(1)
else:
return(slowfib(n-1)+slowfib(n-2))
In [ ]:
# FASTFIB
def fastfib(n):
if n<0:
return(0)
elif n==0:
return(0)
elif n==1:
return(1)
else:
a=1
b=0
i=2
for i in range(2,n+1):
t=a
a=a+b
b=t
return(a)
In [ ]:
from timeit import default_timer as timer
from datetime import timedelta
start = timer()
# function call
end = timer()
print(timedelta(seconds=end-start))
0:00:00.000026
In [ ]:
start = timer()
print (slowfib(7))
end = timer()
print(timedelta(seconds=end-start))
0:00:00.000079
In [ ]:
start = timer()
fastfib(6)
end = timer()
print(timedelta(seconds=end-start))
0:00:00.000134
In [ ]: