Matrix chain multiplication: Difference between revisions
m
→Memoized recursive call
Line 113:
=== Memoized recursive call ===
The only difference between optim2 and optim3 is the [[:wp:https://en.wikipedia.org/wiki/Memoization|@memoize]] [https://www.python.org/dev/peps/pep-0318/ decorator]. Yet the algorithm is way faster with this. According to Wikipedia, the complexity falls from O(2^n) to O(n^3). This is confirmed by plotting log(time) vs log(n) for n up to 580 (this needs [https://docs.python.org/3/library/sys.html#sys.setrecursionlimit changing Python's recursion limit]).
<lang python>def memoize(f):
| |||