Matrix chain multiplication: Difference between revisions
Content added Content deleted
Line 113: | Line 113: | ||
=== Memoized recursive call === |
=== 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). |
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. |
||
<lang python>def memoize(f): |
<lang python>def memoize(f): |