[알고리즘] 분할 정복 - 행렬의 곱셈, 마스터 정리, 쉬트라쎈

💡 행렬

 - m x n 개의 원소를 갖는 사각형 배열 (m: 행, n: 열)

 - 행,열의 수가 같으면 정방행렬

 

 

💡 행렬의 곱

 - A 행렬과 B 행렬이 있을 때, A행렬의 가로와 B행렬의 세로의 원소를 하나씩 곱해 더함

 

  A11 A12      B11 B12       C11 C12

  A21 A22       B21 B22       C21 C22

  C11 = A11xB11 +A12xB21

 

int* matrix( int N, int a[][],  int b[][]) {

	for (int i = 0; i < N;i++)
		for (int j = 0; j < N; j++)
		{
			c[i][j] = 0;
			for (int k = 0; k < N; k++) {
				c[i][j] = c[i][j] + a[i][k] * b[k][j];
			}
		}
}

 

✔️시간 복잡도

 - 덧셈의 관점:  T(n) = (n-1)xnxn = n^3-n^2 ,  O(n^3)

 - 곱셈의 관점:  T(n) = nxnxn = n^3 ,  O(n^3)

 

 

 

💡 쉬트라쎈 행렬 곱

 - 크기가 커지면 쉬트라쎈 행렬곱 방법이 더 이득 

 - 배열의 크기가 임계값보다 크면 쉬트라쎈 방법, 그렇지 않으면 일반적인 방법을 사용

void recurmat(int n, int  A[][], int B[][], int* C[][] ){

	if(n<=임계값)
    	단순한 알고리즘 사용해 C = A*B 계산
    else{
    	A를 4개의 부분행렬로 분할
        B를 4개의 부분행렬로 분힐
        쉬트라센 방법을 사용해 C = A*B 계산
    }

✔️시간복잡도 

 - T(n)=7×T(2n​)+18×(2n​)2

 

 

💡 마스터 정리

 - 재귀식으로 표현한 알고리즘의 동작 시간을 점근적으로 계산하는 방법 ex)쉬트라쎈 행렬 곱셈

 -  T(n) = a*T(n/b) + c*n^k (a,c>0,  b>=2,  n=2^k) , T(1) =1

     

   T(n) = O(n^k) , a<b^k

   T(n) = O(n^k*logn) , a=b^k

   T(n) = O(n&log(b)a) , a>b^k

 

 

http://www.secmem.org/blog/2021/03/20/strassen-algorithm/