15. matrix multiplication [9 1주차]

15. Matrix Multiplication [9-1주차]

2024년 1월 13일 토요일

오후 11:12

 

n x n 행렬 간의 곱 연산의 시간복잡도

총 n²의 원소를 구해야 함. 한 원소를 구하는 데 n번의 곱 연산 필요.

-> O(n³)

 

O(n³)보다 빠르게 구할 수 있을까?

 

 

<Divide and conquer를 이용한 알고리즘>

하나의 행렬을 n/2 x n/2 행렬 네개로 분할한다.

 

8번의 재귀 호출을 수행한다.

 

하나의 재귀 호출에 T(n/2)시간이 걸린다. 덧셈 연산에는 O(n²) 시간이 걸린다.

 

T(n) = 8T(n/2) + O(n²) = O(n³)

분할정복을 이용해도 여전히 O(n³)이 걸린다.

 

행렬 간의 연산 과정에 같은 곱의 쌍이 존재하지 않는다. 따라서 사람들은 O(n³)보다 빠른 알고리즘이 존재하지 않을 것이라고 생각했다.

그러나 스트라센이 O(n³)보다 빠른 알고리즘을 개발하였다.

 

 

<Strassen's Algorithm>

행렬을 n/2 x n/2 행렬로 분할한 후, 덧셈과 뺄셈 연산을 통해 다음을 구한다.

 

이후 7번의 곱셈 연산을 통해 아래의 P₁ ~ P₇ 을 구한다.

 

그러면 놀랍게도, 다음이 성립한다.

 

총 7번의 재귀적인 곱셈 연산으로 전체 행렬의 곱을 구할 수 있다.

 

T(n) = 7T(n/2) + O(n²)

-> O(n^log7) = O(n^2.807…)

 

최근까지 스트라센 알고리즘보다 빠른 알고리즘이 나오고 있다.