In computing, memoization is an optimisation technique used primarily to speed up
computer programs by caching the function results so that, later we can use that result,
when we call the function with the same arguments.
To explore memoization, lets consider the code segment for finding out the term of a
Fibonacci series:
def fib(n):
if n<2:return n
else:
n=fib(n-1)+fib(n-2)
return n
Run the following command to find out the time taken for finding the nth term of the series
$ time python file_name.py
So we would find out then that the time complexity of our program is O(exp(n)) .
Try and find out the 40th term of the Fibonacci series . This code segment will make you
wait for a considerable amount of time before you view your result in the terminal.
Is it possible to find out higher terms of the series much faster???
oh,yes!!
Here is the role of memoization.It caches the results that have been calculated earlier and
stores them in a lookup table so that these don’t have to be calculated again. We make use
of an associative array as a lookup table here.
The following code segment shows the memoized version:
table={0:0,1:1}
def fib1(n):
if not n in table:
table[n]=fib1(n-1)+fib1(n-2)
return table[n]
Run
$ time python file_name.py
Using this memoized function we would find out the higher terms of the series much faster.
But don’t forget everything has a reasonable limit
one-zero 