Matrix Multiplication (Strassen’s Algorithm)

---

01. Matrix Multiplication by Divide-and-Conquer

• 행렬 곱 연산시, 3중 for문 사용 -> Θ(n^3)
• 분할정복으로 계산: 4개씩 정사각형으로 나누어서 연산하고 합치는 과정

size는 작아졌지만 곱셈, 덧셈 횟수는 2번씩 늘어나게 됨 (곱셈: n/2 x n/2)(덧셈: 동일)

 

merge sort처럼 진짜 메모리상에서 partition하는게 아니라 index만 구하는 거임

 

• 각 재귀식 라인마다 T(n/2) size임 -> 8줄이니 8T(n/2)가 됨
• 더하는 과정: (n/2) x (n/2) = (n^2/4)만큼의 덧셈이 필요함 ⇒ Θ(n^2)
• total time

 
-> Master Method로 풀면 Θ(n^3) -> 분할정복을 해도 행렬 곱은 똑같이 Θ(n^3)으로 나오는게 핵심
 
 
 

---

02. Strassen’s Method

• a값을 줄이는 걸 목표로 함 → 8T()는 큰 문제가 8개로 나눠진다는 뜻이니 그걸 7로 줄이자(곱셈 줄이는 대신 덧셈 조금 늘어나긴 함)

덧셈은 늘어나도 n^2가 제일 커서 영향 안 미침

n^3 보다는 무조건 빠르다, 미만이라는 뜻으로 스몰 오 표기

 
 
 

---