Memoization is a method of programming used to optimize a function. Memoization is a form of caching and is related to dynamic programming.
In memoization, a function stores the value that it has calculated for the given arguments. If the function is recalled with the same arguments, the result does not have to be recalculated, but can be returned immediately. Example: the Fibonacci series
The C function below calculates the nth Fibonacc number (without memoization): int fib(int n) { if (n < 1) return 0; if (n == 1) return 1; return fib(n-1) + fib(n-2); }
When we use memoization, the function may look like this: int fib2(int n) { static int r[10000]; int t; if (n < 1) return 0; if (r[n]) return r[n]; if (n == 1) t = 1; else t = fib2(n-1) + fib2(n-2); return r[n] = t; }
For the calculation of the 10th, 20th and 40th fibonacc numbers, the first function is called recursively, respectively 176, 21,890 and 331,160,280 times. The second, memotic function only requires recursive calls, respectively, 18, 38 and 78. By applying memoization, the duration of the function has been reduced from exponential ( O ( x n ) {\displaystyle O(x^{n})} ) to linear ( O ( n ) {\displaystyle O(n)} ).
wiki
