Re: Prediction of local code modifications

Chris F Clark wrote:
(snip)


> It is worth noting, that because of the required backtracking, dynamic
> programming solutions usually grow exponentially with input problem
> size. That is, if your problem adds one more binary decision to the
> previous problem, the new problem takes roughly twice as long to
> solve, because you have doubled the size of tree you have to explore
> to find the correct solution.


In most cases dynamic programming solutions don't grow exponentially,
though that may not be true in all cases. Usually they solve in
polynomial time something that would seem to be exponential.


For problems like the biology two sequence comparison or the diff two
file comparison it is O(m*n) where m and n are the two sequence or
file lengths. (Diff computes a hash for each line and then applies
dynamic programming to the list of hash values, so it is O(m*n) in
file lines.)


-- glen

Return to the comp.compilers page.
Search the comp.compilers archives again.