Chained Matrix Multiplication

💫 Chained Matrix Multiplication

---

연쇄 행렬 곱셈

행렬 곱셈의 특성

행렬의 곱셉을 할때의 예를 들어보자 A X B 일 때
A의 열과 B의 행의 수는 같아야한다.

계산을 할때 k+1 > j 를 넘어가서는(k+1≤j) 안되므로 k < j 어야 한다.

📁 수도 코드

int minmult(int n, const int d[], index P[][]) {
  index i, j, k, diagonal;
  int M[1..n, 1..n];
  for(i=1; i <= n; i++)
    M[i][i] = 0;
  for(diagonal = 1; diagonal <= n-1; diagonal++)
    for(i=1; i <= n-diagonal; i++) {
        j = i + diagonal;
		M[i][j] = minimum(M[i][k]+M[k+1][j]+d[i-1]*d[k]*d[j]); 
        //i <= k <= j-1 반복
        P[i][j] = 최소치를 주는 k의 값 
  }
  return M[1][n];
}
void order(index i, index j) 
{ 
	if (i == j) 
    	cout << “A” << i;
    else {
        k = P[i][j];
	} 
}

최적 분해는 처음에 P[1][6]을 시작으로 계속 K값의 위치에 따라 계속 추가하면 된다.

ex)
P[1][6] = 1 $A_1(A_2A_3A_4A_5A_6)$ ← 1과 2~6으로 나누었으니 다음으로 2~6에서의 계산 우선순위를 보면된다.

따라서 P[1][6] → P[2][6] → P[2][5] →P[2][4]
최적 분해 = $(A_1(((A_2A_3A_4)A_5)A_6))$

📁 시간 복잡도

시간 복잡도 : $n^2$