Suhwanc

[종만북] 행렬의 거듭제곱

우리가 보통 행렬의 곱셈을 구현하기 위해서는 n x n 행렬이 A, B가 있을 때 주어진 행렬의 모든 원소(n^2 가지)에 대해 A행렬의 가로, B행렬의 세로를 곱해줘야 하기 때문에 O(n^3) 번의 연산이 필요하게 된다. 이렇게 되면 n이 조금만 커져도, 또는 거듭제곱의 수가 조금만 커져도 필요한 연산의 수가 매우 크게 증가하기 때문에 연산의 수를 줄이는 알고리즘이 필요하다. 우리는 이 문제를 분할 정복(divide & conquer)로 해결할 수 있는데 예를 들어 행렬 A를 m번 거듭 제곱한다 하면, A^(m) = A^(m/2) * A^(m/2)로 나눌 수 있다는 점을 이용한다. (행렬의 곱셈법칙에 따라서) 만약 A^8 를 구하기 위해 곧이곧대로 A를 7번 곱하게 되면 연산은 총 7 * n^3번 해야..