Memoization is a technique to increase the time performance of an algorithm by using some extra memory.
According to Wikipedia:
In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
As an example lets write a method that calculates the nth Fibonacci number:
1 2 3 4 5 6 |
func fib(_ n: Int) -> Int { if (n < 2) { return n } return fib(n - 1) + fib(n - 2); } |
This method recursively calls itself till n becomes less than 2.
In order to use the Memoization technique we have to create an extra array with the stored results values, We can write the algorithm as follows:
1 2 3 4 5 6 7 8 9 10 11 12 |
func fibWithMemoization(_ n: Int) -> Int { var memoization = Array(repeating: -1, count: n + 1) memoization[0] = 0 memoization[1] = 1 for i in 2...n { memoization[i] = memoization[i - 1] + memoization[i - 2] } return memoization[n] } |
The time complexity now becomes O(n) and so does the space complexity.