memoisation.py

Created by schraf

Created on October 13, 2020

475 Bytes

from time import monotonic

# Nieme nombre de Fibonacci
N = 30

# version classique

def fib(n):
   if n == 1 or n == 2: return 1
   return fib(n-1) + fib(n-2)

t = monotonic()
fib(N)
print(monotonic() - t)

# version memoisation

table = {}

def memofib(n):
  global table
  if n not in table:
      if n == 1 or n == 2: table[n] = 1
      else: table[n] = memofib(n-1) + memofib(n-2)
  return table[n]

t = monotonic()
memofib(N)
print(monotonic() - t)