[Algorithm] 분할정복(3) - Matrix Multiplication

🤔 분할정복

분할정복이란 일반적으로 주어진 문제를 작은 단위로 분할한 뒤 분할된 문제들을 재귀적으로 해결하여 해당 답을 적절하게 조합하여 큰 문제의 답을 제시하는 알고리즘을 말합니다.

 

이때 분할된 문제들을 조합하여 큰 문제를 해결하는 것을 Conquer이라고 합니다.

 

알고리즘의 Basic Arithmetic의 연장선인 행렬곱을 알고리즘의 관점에서 알아보겠습니다.

 

행렬에 대한 알고리즘 공부가 하기 싫어서 미루고 있다 이제야 포스팅 하게 되었습니다.

 

행렬 중에서도 두 $n\times{n}$ Matrix의 경우만 알아보도록 하겠습니다.

 

 

 

 

 

 

 

 

 

 

 

🔎 두 $n \times n$ Matrix 곱하기 연산

 

먼저 행렬의 각 entry들 간의 사칙연산은 모두 $O(1)$시간이 걸린다고 하겠습니다.

 

예시로 아래의 행렬을 통해 두 $n \times n$ 행렬을 곱하는 데에 필요한 시간복잡도에 대해 알아보겠습니다.

 

 

 

 

 

 

✍️ Solution 1

 

위 예시에서 $c_1 = a_1b_1 + a_2b_4 + a_3b_7$ 이 되며, 이는 총 2번의 addition 과 3번의 multiplication 연산이 필요합니다.

 

다른 entry 를 구하는데도 마찬가지로 같은 연산이 필요한데 모든 entry의 개수는 9개이므로 $(2 + 3) \times 9$의 시간이 걸리는 것을 알 수 있습니다.

 

이를 일반화 하면 $n - 1$번의 addition 연산과 $n$번의 multiplication 연산이 필요합니다.

 

즉, addition 연산과 multiplication 연산은 $O(n)$의 시간복잡도를 가지는 것을 알 수 있습니다.

 

또한 entry의 총 개수는 $n^2$개 이므로 총 소모시간은

 

$$O(n) \times n^2 = O(n^3)$$

 

임을 알 수 있습니다.

 

 

 

 

 

 

✍️ Solution 2

 

Divide and Conquer를 이용하여 같은 행렬 곱을 더 빠른 시간에 실행할 수 있습니다.

 

 

 

위와 같은 $n \times n$행렬 X와 Y가 존재할 때 이를 $n/2 \times n/2$행렬(submatrix) 4개로 나눌 수 있습니다.

 

나누어진 행렬을 각각 "A ~ H"라고 하겠습니다.

 

두 행렬 X와 Y를 곱해져 얻어진 행렬을 XY라고 하면 아래의 그림과 같은 행렬을 얻을 수 있습니다.

 

 

 

 

이제 시간 복잡도를 구해볼 차례입니다.

 

$n/2 \times n/2$ 연산이 (AE, BG, AF, BH, CE, DG, CF, DH) 총 8번 진행되므로  $8T(n/2)$로 나타낼 수 있습니다.

 

또한 submatrix하나당 addition이  $(n/2)^2$번 만큼 진행되므로 $O(n^2)$으로 나타낼 수 있습니다.

 

따라서 Divide and Conquer를 이용하면

 

$$T(n) = 8T(n/2) + O(n^2)$$

 

와 같이 나타낼 수 있고 Master Theorem에 조건을 확인했을 때 $log_28 = 3 > 1$ 이므로 $T(n)$의 일반해는 $O(n^2)$임을 알 수 있습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

✍️ Solution 3

더 빠른 알고리즘인 Strassen 알고리즘이 존재하는데 이는 아래의 링크를 참조해주시기 바랍니다.

 

 

 

https://ko.wikipedia.org/wiki/%EC%8A%88%ED%8A%B8%EB%9D%BC%EC%84%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

슈트라센 알고리즘 - 위키백과, 우리 모두의 백과사전

 

 

 

 

참고로 현재 가장 빠른 알고리즘은 $O(n^{2.378596})$의 시간복잡도를 가진다고 합니다.

 

 

 

 

 

 

 

 

 

 

다음 포스팅에서는 Selection 알고리즘에 대해 배워보겠습니다.