Thu, 03 Apr 2008 00:02:21 -0800

Related articles |
---|

[4 earlier articles] |

Re: Prediction of local code modifications gah@ugcs.caltech.edu (glen herrmannsfeldt) (2008-03-29) |

Re: Prediction of local code modifications preston.briggs@gmail.com (preston.briggs@gmail.com) (2008-03-29) |

Re: Prediction of local code modifications plfriko@yahoo.de (Tim Frink) (2008-04-01) |

Re: Prediction of local code modifications preston.briggs@gmail.com (preston.briggs@gmail.com) (2008-04-01) |

Re: Prediction of local code modifications max@gustavus.edu (Max Hailperin) (2008-04-02) |

Re: Prediction of local code modifications cfc@shell01.TheWorld.com (Chris F Clark) (2008-04-02) |

Re: Prediction of local code modifications gah@ugcs.caltech.edu (glen herrmannsfeldt) (2008-04-03) |

Re: Prediction of local code modifications max@gustavus.edu (Max Hailperin) (2008-04-03) |

Re: Prediction of local code modifications plfriko@yahoo.de (Tim Frink) (2008-04-03) |

Re: Prediction of local code modifications find@my.address.elsewhere (Matthias Blume) (2008-04-04) |

Re: Prediction of local code modifications gneuner2@comcast.net (George Neuner) (2008-04-04) |

Re: Prediction of local code modifications cfc@shell01.TheWorld.com (Chris F Clark) (2008-04-04) |

Re: Prediction of local code modifications cfc@shell01.TheWorld.com (Chris F Clark) (2008-04-05) |

[3 later articles] |

From: | glen herrmannsfeldt <gah@ugcs.caltech.edu> |

Newsgroups: | comp.compilers |

Date: | Thu, 03 Apr 2008 00:02:21 -0800 |

Organization: | Compilers Central |

References: | 08-03-105 08-03-109 08-04-003 08-04-009 |

Keywords: | code, optimize |

Posted-Date: | 03 Apr 2008 10:21:23 EDT |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.