kingofnumbers's blog

Matrix chain multiplication O(N log N)
By kingofnumbers, 11 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

»
11 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

→ Reply
»
6 years ago, # |
  Vote: I like it +24 Vote: I do not like it

It took me more than a hundred lines:

https://gist.github.com/johnchen902/44d9c5be53154aec4acf685c41c88a81

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply