MEMOIZATION-
A technique to store the partial results in the function call .Which results in the reduction of the time interval of the function execution. Consider the case of the fibonacci series.
Let there be a function call of fibo(6) then this function will further call the fibo(5) and fibo(4) and in a similar way the fibo(5) will be calling fibo(4) and fibo(3). If you continue with this you will notice that their is repetition of the function calls i.e for example fibo(2) will be called by both the fibo(4) and fibo(5) functions. which leads to the overlapping and wastage of the very imp. time . Hence not giving fast response on large inputs . In order to improve this we use the concept of reducing the function execution time in exchange of the function's space complexity which is commonly known as memoization a well defined technique.
Consider a recursive factorial function used to calculate the factorial of the entered number recursively below is the rough code which is just for the analysis
function factorial (n is a non-negative integer)
if n is 0 then
return 1 [by the convention that 0! = 1]
else
return factorial(n-1) times n [recursively invoke factorial
with the parameter 1 less than n]
end if
end function
In this case on first function call if will take the as usual time it should take , on returning the results it has no results in it's account . example it don't remember 3! . What happens is that on next function call this function has to repeat the whole process , takes again the same time for factorial i.e it has to again calculate the fact 3 which is equal to 6. Now what we are doing is recalculating the previously calculated results , which leads to a dramatic changes in the functions time complexity. Imagine how it could be if it is assumed the recalculations are not performed , ya it is possible. From the above situation one can think of some trick that is their any way to store the previously solutions , just before making the down function call , check the store array for the result of that down function call. If it contains the result than use it , it will reduce a lot effort going to be made on calculation , otherwise allow the function to call the down function . At the end don't forget to store the result in the store array.
below is the memoized version of the factorial function
function factorial (n is a non-negative integer)
if n is 0 then
return 1 [by the convention that 0! = 1]
else if n is in lookup-table then
return lookup-table-value-for-n
else
let x = factorial(n-1) times n [recursively invoke factorial
with the parameter 1 less than n]
store x in lookup-table in the nth slot [remember the result of n! for later]
return x
end if
end function
So here i can say that the memoization is buying me a tremendous advantage.
Here we to look up at the table of which memoization is the special case.
when you do something complicated you save the answers and then you go get it later.
That's all about memoization.
-krishna agarwal
