재귀함수를 이용해서 행렬의 곱 구하기

#include <stdio.h>
#include <stdlib.h>

void matrix_mul(int** matrix_A, int** matrix_B, int** matrix_C, int len, int i, int j, int k)
{
    /* 행렬의 길이가 2일때 행렬곱 계산하고 종료하기 */
    if (len == 2)
    {
        matrix_C[i][k] += matrix_A[i][j]* matrix_B[j][k] + matrix_A[i][j + 1]* matrix_B[j + 1][k];
        matrix_C[i][k + 1] += matrix_A[i][j]* matrix_B[j][k + 1] + matrix_A[i][j + 1]* matrix_B[j + 1][k + 1];
        matrix_C[i + 1][k] += matrix_A[i + 1][j]* matrix_B[j][k] + matrix_A[i + 1][j + 1]* matrix_B[j + 1][k];
        matrix_C[i + 1][k + 1] += matrix_A[i + 1][j]* matrix_B[j][k + 1] + matrix_A[i + 1][j + 1]* matrix_B[j + 1][k + 1];
        return;
    }

    /* 행렬의 길이가 2를 초과할때 재귀적 호출하기*/
    else
    {
        matrix_mul(matrix_A, matrix_B, matrix_C, len/2, i, j, k);
        matrix_mul(matrix_A, matrix_B, matrix_C, len/2, i, j + len/2, k);
        matrix_mul(matrix_A, matrix_B, matrix_C, len/2, i, j, k + len/2);
        matrix_mul(matrix_A, matrix_B, matrix_C, len/2, i, j + len/2, k + len/2);
        matrix_mul(matrix_A, matrix_B, matrix_C, len/2, i + len/2, j, k);
        matrix_mul(matrix_A, matrix_B, matrix_C, len/2, i + len/2, j + len/2, k);
        matrix_mul(matrix_A, matrix_B, matrix_C, len/2, i + len/2, j, k + len/2);
        matrix_mul(matrix_A, matrix_B, matrix_C, len/2, i + len/2, j + len/2, k + len/2);
    }
}

int main() {
    int size = 0, i = 0, j = 0, k = 0;
    printf("입력할 행렬의 행과 열의 수를 입력하세요(2의 n승인 수로):");
    scanf("%d", &size);

    /* 계산할 두개의 행렬 동적 할당 해주기 */
    int** matrix_A = (int**)malloc(sizeof(int) * size);
    for (i = 0; i < size; i++) {
        matrix_A[i] = (int*)malloc(sizeof(int) * size);
    }

    int** matrix_B = (int**)malloc(sizeof(int) * size);
    for (i = 0; i < size; i++) {
        matrix_B[i] = (int*)malloc(sizeof(int) * size);
    }

    int** matrix_C = (int**)malloc(sizeof(int) * size);
    for (i = 0; i < size; i++) {
        matrix_C[i] = (int*)malloc(sizeof(int) * size);
    }

    /* 행렬 입력받기 */
    printf("첫번째 행렬을 입력하세요\n");
    for (i = 0; i < size; i++) {
        printf("%d번째 행:", i + 1);
        for (j = 0; j < size; j++) {
            scanf("%d", &matrix_A[i][j]);
        }
        fflush(stdin);
    }

    printf("두번째 행렬을 입력하세요\n");
    for (i = 0; i < size; i++) {
        printf("%d번째 행:", i + 1);
        for (j = 0; j < size; j++) {
            scanf("%d", &matrix_B[i][j]);
        }
        fflush(stdin);
    }
    /* 행렬 초기화시켜 주기*/
    for (i = 0; i < size; i++) {
        for (j = 0; j < size; j++) {
            matrix_C[i][j] = 0;
        }
    }

    matrix_mul(matrix_A, matrix_B, matrix_C, size, 0, 0, 0);//재귀함수 호출

    /* 결과 값 출력해주기 */
    for (i = 0; i < size; i++) {
        for (j = 0; j < size; j++) {
            printf("%d ", matrix_C[i][j]);
        }
        printf("\n");
    }

    free(matrix_A);
    free(matrix_B);
    free(matrix_C);
}

시간 복잡도 계산

n의 길이를 가지는 행렬을 내적할 때의 시간복잡도를 T(n)이라고 하면 T(n) = T(divide) + T(conquer) + T(merge)로 나타낼  수 있다.

T(divide) = 1이고, n/2의 길이를 가지는 행렬의 곱을 8번 수행해야하기 때문에 T(conquer) =8T(n/2),

n x n 크기의 행렬의 각각의 원소에 대한 덧셈을 수행해야 함으로 T(merge) = n^2이다.
따라서

 

 

 

 

 

등비수열의 합 공식에 의해서  위 식의 합은

이고, 

 

 

시간복잡도는

이다.