[중간고사] 2-(2). Divide and Conquer - Matrix Multiplication

1. Iterative Algorithm

• C = AB, (이때, n * m 크기의 행렬 A,  m * p 크기의 행렬 B → n * p의 크기의 행렬 C)

 

• 시간복잡도
  • 위의 알고리즘은 Θ(npm)의 시간 복잡도를 가짐.
    즉, 일반적으로 Θ(n^3)의 시간 복잡도를 가짐. (for문 3개인 거 확인 가능)

2. Divide and conquer Algorithm (Brute force)

• 2^n의 크기를 가지는 동일한 행렬 A, B에 대해 수식은 다음과 같음.

• 다음에 따라 8번의 곱셈과 4번의 덧셈이 필요하다는 것을 알 수 있음.
  즉, 8개의 n/2 크기의 부분 행렬의 곱과 그들의 합 Θ(n^2) 으로 이뤄질 수 있음.
• 시간복잡도

• 위 수식으로 풀면,  Θ(n^3)의 시간 복잡도를 가지며,
  Iterative 알고리즘과 동일한 시간 복잡도를 가진다는 것을 알 수 있음.

3. Strassen Algorithm ( 슈트라센 )

(1) X, Y, Z 설정	(2) M 계산 (7번 곱셈 + 18번의 덧셈)	(3) Z의 I, J, K, L 계산

 

• 시간복잡도

• 곱셈을 더 적게 하는 것은? 슈트라센
• 그러므로 2 * 2 행렬곱에서 best임!!!