VietMX Staff asked 3 years ago
Why? Any problems you may face with that solution?
Yes. It’s called Memoization. Memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls.
Let’s look at the diagram that will help you understand what’s going on here with the rest of our code. Function fib is called with argument 5. Can you see that we calculate the fib(2) results 3(!) times?
Basically, if we just store the value of each index in a hash, we will avoid the computational time of that value for the next N times. This change will increase the space complexity of our new algorithm to O(n) but will dramatically decrease the time complexity to 2N which will resolve to linear time since 2 is a constant O(n).
There’s just one problem: With an infinite series, the memo array will have unbounded growth. Eventually, you’re going to run into heap size limits, and that will crash the JS engine. No worries though. With Fibonacci, you’ll run into the maximum exact JavaScript integer size first, which is 9007199254740991. That’s over 9 quadrillion, which is a big number, but Fibonacci isn’t impressed. Fibonacci grows fast. You’ll burst that barrier after generating only 79 numbers.
function fibonacci(num, memo) { memo = memo || {}; if (memo[num]) return memo[num]; if (num <= 1) return 1; return memo[num] = fibonacci(num - 1, memo) + fibonacci(num - 2, memo);}