Блог пользователя BabuRao

Help with Matrix Chain Multiplication
Автор BabuRao, история, 5 лет назад, По-английски

I was reading about the matrix chain multiplication problem and came across an $$$O(N^2)$$$ solution on GeeksforGeeks.

The link to the same is here

However the blog had this note: Note : Below solution does not work for many cases. For example: for input {2, 40, 2, 40, 5}, the correct answer is 580 but this method returns 720.

So, I was wondering how accurate is the solution and do any questions of MCM require $$$O(N^2)$$$ optimization? Any help is appriciated.

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

This algorithm is wrong as it doesn't consider many parenthesis.

Example : For $$$n = 2^k$$$, the algorithm doesn't consdier the case, when you multiply $$$M_{2i}, M_{2i + 1} $$$ , for all $$$i$$$, and recursively multiply the remaining $$$2^{k - 1}$$$ matrices.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thank you!

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Were you able to find any O(n2) correct solution ??

      → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        No, as fugazi said that the n^2 algo is wrong and I didn't look for any N^2 algo since I was just reading about MCM and not solving any problem. I don't think it is possible to solve the problem in less than N^3

        → Ответить