연쇄 행렬 최소 곱셈 알고리즘(Chained Matrix Multiplication)
" Foundations of Algorithms, Fifth Edition : Neapolitan, Richard " 자료를 참고하여 작성했습니다. 연쇄 행렬 최소 곱셈 알고리즘은 주어진 행렬들의 곱을 진행할 때 최소의 연산 횟수를 구하는 알고리즘이다. 행렬은 곱셈 과정에서 어떻게 결합되어 연산하느냐에 따라 연산 횟수가 달라진다. 예를 들어, 순서대로 곱셈을 할 수 있는 행렬 4개 A, B, C, D 가 주어진다고 가정하자. A : i x j B : j x k 행렬이라 예를 들면, A x B 의 연산 횟수 = i x j x k 번 이렇게 계산된다. 그럼 위의 예시 A, B, C, D 행렬의 곱을 진행할 때 결합 순서에 따라 다르게 진행하면 아래와 같이 연산 횟수가 천차만별로 차이가 난다...
2023. 6. 11.
