Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Re: Re: Puzzle: need a more general algorithm

by Anonymous Monk
on Jul 10, 2002 at 12:35 UTC ( #180735=note: print w/ replies, xml ) Need Help??


in reply to Re: Puzzle: need a more general algorithm
in thread Puzzle: need a more general algorithm

Very good. Pre-memoization you are exponential. With memoization your memory usage scales like O(n**3), and your performance is O(n**4). If you passed the array by reference, and added 2 indices, you would drop a factor of n off of both.

By contrast the efficient algorithm is sub-exponential pre-memoization, and is sub-quadratic after.

Which shows that good algorithms are a big win, but being straightforward, and then applying well-known speedups to that, can still result in a usable algorithm.


Comment on Re: Re: Puzzle: need a more general algorithm

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://180735]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (2)
As of 2015-07-06 03:21 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (70 votes), past polls