Talk:Matrix chain multiplication

From Wikipedia, the free encyclopedia

You have new messages (last change).

[edit] cost of string concatenation

I think it's not justified to say that string concat is O(n+m), one has to distinguish

  • the search for the end token (in O(n), but only READ), and
  • the creation of the new string (requiring
  • memory allocation (which might be more expensive than all the rest, depending on implementation (default MEM_CLEAR or so))
  • COPYING of the first and then the second string (READ + WRITE in another memory segment, O(n+m) operations)

On the other hand, if one uses reference counting and allows for segmented string storage, then the concatenation takes virtually no time.

Concerning "memoization", why the heck did this guy not call it memorization ??? (Or memo'ization ?)

And finally, I would be astonished if there was no better ("local") method for optimizing this matrix problem, rather than checking all possible combinations... I'll think about this... MFH 13:43, 24 Mar 2005 (UTC)

Greedy algorithms don't work well for this problem, because locally optimal solutions may turn out to force a globally poor solution — not that there aren't decent approximation algorithms based on heuristics. If you click on the memoization link, you'll discover that this is not a misspelling, like everyone always assumes (I wish they'd pick a less confusing word). You're right that different approaches to string concatenation take very different amounts of time. This is mostly irrelevent, since the technique works with any cost function, but the specific cost I give is for a C strcat() call without any reallocation (it's assumed sufficient space is available after the first string). Deco 23:15, 24 Mar 2005 (UTC)
Retrieved from "http://en.wikipedia.org../../../m/a/t/Talk%7EMatrix_chain_multiplication_fe1c.html"