4 ms·
> If you memoize you turn either of them into constant time. At the risk of stumbling into the No True Memoization fallacy, I wouldn't consider that memoizing
by gmfawcett 5y ago
> If you memoize you turn either of them into constant time.
At the risk of stumbling into the No True Memoization fallacy, I wouldn't consider that memoizing -- at least not in the dynamic programming sense. To get O(1), you're not temporarily tabling the results during a single run of the algorithm; rather you're building a semi-permanent database of answers and (effectively, in an amortized sense) discarding the algorithm altogether. I think that's formally known as the "just Google it" approach to optimization. :) From a DP perspective you can get O(N) from memoization on open-form Fibonacci, and no gain on open-form factorial, because the lookup table is ephemeral.
- seanhunter 5y agoThis is probably the most "hackernews" conversation I've ever had but as far as I've ever seen the term used, "memoization" is not restricted to temporarily tabling the results during a single run of the algorithm but used to mean any caching of results of an expensive pure function for future use. You seem to call that a "semi-permanent database of answers". Here is the original memoization paper [1] where he is using a constant-time table lookup exactly as I envisage in this case rather than only tabling results during a single invocation of the algorithm. Ironically he uses it to memoize a recursively-defined factorial function. [1] https://www.cs.utexas.edu/users/hunt/research/hash-cons/hash-cons-papers/michie-memo-nature-1968.pdf https://www.cs.utexas.edu/users/hunt/research/hash-cons/hash...
- gmfawcett 5y agolol, yes, we are at Peak HN right now. :) Michie (1968) wins the debate, without a doubt! Thanks for sharing your point of view, and the article.