[알고리즘] Matrix Multiplication

Matrix Multiplication

• 2개의 N x N 행렬들을 곱하는 것
• 일반적인 방법으로는 O(N^3) 의 시간이 걸린다

일반적인 방법에서
더하기는 생각하지 않고 곱하기 횟수만 세면 N^3이고, N^2보다 빠를 수는 없다.

더 빠르게 할 수는 없을까?

• Divide and Conquer로 가능하다

Strassen's Algorithm

정의에 따라 n×n 크기의 두 행렬을 곱하면 O(n^3)의 시간이 소요되지만 이 알고리즘은 대략 O(n^2.807..)의 시간이 소요된다.

정의대로 하면 곱셈을 8번 해야 하는데,
위 알고리즘대로 하면 곱셈을 7번만 하면 된다.

따라서 위와 같이 계산하면 O(N^3)보다 빠르게 되는데,
N이 작을 경우 일반 정의로 계산하는 방법이 더 나을 수 있다고 한다.