[알고리즘 분석] 2장. 분할정복법(divide-and-conquer) (3)

1. 행렬 곱셈(matrix multiplication)

[단순한 행렬곱셈 알고리즘]
- 문제: $ n \times n $ 크기의 행렬의 곱을 구하시오.
- 입력: 양수 n, $ n \times n $ 크기의 행렬 A와 B
- 출력: 행렬 A와 B의 곱인 C
- 알고리즘

void matrixmult (int n, const number A[][], const number B[][], number C[][]){
    index i, j, k;
    for (i = 1; i <= n; i++){
        for (j = 1; j <= n; j++){
            C[i][j] = 0;
            for (k = 1; k <= k++)
                C[i][j] += A[i][k] * B[k][j];
        }
    }
}​

- 시간 복잡도 분석

1) 단위연산: 곱셈
- 모든 경우 시간 복잡도 분석: $ T(n) = n \times n \times n = n^{3} \in \Theta(n^{3}) $

2) 단위연산: 덧셈
- 알고리즘 약간 수정

void matrixmult (int n, const number A[][], const number B[][], number C[][]){
    index i, j, k;
    for (i = 1; i <= n; i++){
        for (j = 1; j <= n; j++){
            C[i][j] = A[i][1] * B[1][j];
            for (k = 2; k <= n; k++)
                C[i][j] += A[i][k] * B[k][j];
        }
    }
}​​

- 모든 경우 시간 복잡도 분석: $ T(n) = n \times n \times (n-1) = n^{3} - n^{2} \in \Theta(n^{3}) $

 

2. 단순한 방법의 2 x 2 행렬 곱셈

$ \begin{bmatrix} c_{11} & c_{12}\\ c_{21} & c_{22} \end{bmatrix} = \begin{bmatrix} a_{11} & a_{12}\\ a_{21} & a_{22} \end{bmatrix} \times \begin{bmatrix} b_{11} & b_{12}\\ b_{21} & b_{22} \end{bmatrix} $

$ = \begin{bmatrix} a_{11} \times b_{11} + a_{12} \times b_{21} & a_{11} \times b_{12} + a_{12} \times b_{22}\\ a_{21} \times b_{11} + a_{21} \times b_{21} & a_{22} \times b_{12} + a_{22} \times b_{22} \end{bmatrix} $

- 8번의 곱셈과 4번의 덧셈이 필요하다.

 

3. 쉬트라센 (Strassen) 방법의 행렬 곱셈

$ \begin{bmatrix} c_{11} & c_{12}\\ c_{21} & c_{22} \end{bmatrix} = 
\begin{bmatrix} a_{11} & a_{12}\\ a_{21} & a_{22} \end{bmatrix} \times 
\begin{bmatrix} b_{11} & b_{12}\\ b_{21} & b_{22} \end{bmatrix} $

쉬트라센의 해 C
$ C = \begin{bmatrix} m_{1} + m_{4} - m_{5} + m_{7} & m_{3}+m_5 \\ m_2 + m_4 & m_1 + m_3 - m_2 + m_6 \end{bmatrix} $

$ m_1 = (a_{11} + a_{22}) \times (b_{11} + b_{22}) $
$ m_2 = (a_{21} + a_{22}) \times b_{11} $
$ m_3 = a_{11} \times (b_{12} - b_{22}) $
$ m_4 = a_{22} \times (b_{21} - b_{11}) $
$ m_5 = (a_{11} + a_{12}) \times b_{22} $
$ m_6 = (a_{21} - a_{11}) \times (b_{11} + b_{12}) $
$ m_7 = (a_{12} - a_{22}) \times (b_{21} + b_{22}) $

- 7번의 곱셈과 18번의 덧셈/뺄셈이 필요하다.
- 행렬의 크기가 커지면 단순한 방법보다 쉬트라센 방법이 더 효율적이다.
- n이 2보다 더 큰 2의 거듭제곱이라고 할 때, 각 행렬을 4개의 부분행렬을 나누어 쉬트라센 방법을 통해 M을 구하고, 이를 또 쉬트라센 방법을 통해 n x n 행렬을 곱셈하게 된다.

 

4. 쉬트라센의 알고리즘

- 문제: n이 2의 거듭제곱일 때, n x n 크기의 두 행렬의 곱을 구하시오.
- 입력: 정수 n, n x n 크기의 행렬 A와 B
- 출력: 행렬 A와 B의 곱인 C
- 알고리즘

void strassen (int n, n*n_matrix A, n*n_matrix B, n*n_matrix& C){
    if (n <= threshold)
        단순한 알고리즘을 사용하여 C = A * B를 계산
    else {
        A를 4개의 부분행렬 A11, A12, A21, A22로 분할
        B를 4개의 부분행렬 B11, B12, B21, B22로 분할
        쉬트라센 방법을 사용하여 C = A * B를 계산
    }
}​

[시간복잡도 분석]
1) 단순한 방법: 모든 경우 분석 
- 단위연산: 곱셈
$ T(n) = 8T(\frac{n}{2}), n > 1, n = 2^k (k \geq 1) $

$ T(1) = 1 $

$ T(n) = 8^k = n^3 $

$ T(n) = n^{3} \in \Theta(n^{3}) $


2) 쉬트라센 방법: 모든 경우 분석
- 단위연산: 곱셈
$ T(n) = 7T(\frac{n}{2}) $

$ T(1) = 1 $

$ T(n) = 7 \times 7 \times ... \times 7 (k번) $

$ = n^{lg 7} = n^{2.81} \in \Theta(n^{2.81}) $


- 단위연산: 덧셈/뺄셈
$ T(n) = 7T(\frac{n}{2}) + 18(\frac{n}{2})^2 $

$ T(n) = 6n^{lg_{2}{7}} - 6n^2 \in \Theta(n^{2.81}) $

-> 행렬의 크기가 커질 수록 쉬트라센 알고리즘이 더 효율적이다.