Fibonacci: Iterative, recursion, memoization, Matrix exponentiation--NOT OPTIMAL OOP--Scared, ATH
#shorts
Problem statement: https://codeforces.com/gym/102644/pro...
Solution: https://github.com/Mourad-NOUAILI/cod...
------------------
Imagine that you task is to compute the n-th term of the Fibonacci sequence, where n is BTW 0 and 10^18.
You can implement a iterative brute force solution. In this case, for huge ns, you'll wait a long time before you see a result, because its time complexity is O(n),
The recursive solution is worst. Not only because its O(2^n) time complexity, also because the call stack overflow,
You can fixed with memoization, to reduce the time complexity to O(n), but the space complexity will be O(n) o_O Really...
The best way is to use matrix exponentiation. Hey, hey, the time complexity is reduce to O(log n) and the space complexity is constant.
If you want a deep explanations of these all stuffs, just let me know in comments :)