> Le 14 janv. 2014 à 21:02, Shashwat Anand a écrit : > >> I just found that trying to consume the minimal memory (n+1) was >> significantly >> slower than using (2n) IIRC. >> > Just someone curious here. > > Assuming two strings of length M and N, we can do the naive edit distance via > dynamic programming, > in O (MN) time and O (MN) space. > > However since only last row is used to determine the result, we can save the > space by using O (N) memory, > which is basically 2*N memory. > > What I don't understand is, what is this minimal memory (n + 1) you just > mentioned ?
Assuming you have computed row P from 1 to Q (included) , you don't need the values of row P-1 from 1 to Q (excluded) anymore. So you can use a circular buffer. So you store Q+N-(Q-1) = N+1 values. See https://en.wikipedia.org/wiki/Longest_common_subsequence_problem Reduce the required space section (they don't explain why exactly but once you see the matrix you'll get it) I also found that "Dynamic Programing" is an over-used term. -- M
