kingofnumbers's blog

By kingofnumbers, 8 years ago, In English

Hi, I read in this article that Matrix chain multiplication problem can be solved with O(N log N) by transforming it into the problem of partitioning a convex polygon into non-intersecting triangles.

but how can this done? do you know the details of O(N log N) solution?

thanks.

 
 
 
 
  • Vote: I like it
  • +12
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +28 Vote: I do not like it

There is a link at the Wiki-page to the corresponding article with implementation details: ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/81/875/CS-TR-81-875.pdf

»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wow, fascinating stuff!! Thanks a lot for sharing.