점화식의 고속 계산

보통의 점화식의 경우, 매 항의 값을 식의 정의를 통해 구하게 된다. 하지만 구하고자하는 항이 10억번째 항과 같이 매우 큰 수번째 항을 구해야 하는 경우, 모든 값을 일일이 계산하기엔 처리 속도에서 문제가 생긴다.

하지만 최대 10억번째 항까지의 값이 필요하다고 해도 한 개의 항의 값만 필요하거나 그 범위 내 10만개 등 몇 개의 항의 값만을 알아내야한다면 전체를 다 계산하는 것이 아닌, 일부를 계산하는 방법으로 해결할 수 있다.

 

행, 열의 길이가 최대 m인 행렬로 표현 가능한 점화식의 한 항을 O(lgN * m^3)에 해결할 수 있는 방법

 

위와 같이 주어진 점화식이 있을 경우, 이를 행렬로 다음과 같이 표현 가능하다.

이 때, 

라 정의하면, 행렬의 거듭제곱의 성질을 이용하면

임을 알 수 있고, 이로써 A^n을 알고 있으면 A^n과 (a3, a2, a1)의 곱을 통해 a_(n+3)을 구할 수 있다.

이 때의 행렬의 곱연산은 3^3(m^3, 이 경우 m = 3) 상수시간에 할 수 있으므로 A^n을 빠르게 구하기만 하면 된다.

 

행렬의 결합법칙에 의해 짝수인 n에 대해 A^n = A^(n/2) * A^(n/2) 임을 알 수 있으므로(홀수의 경우 A를 한 번 더 곱한다)

A^n = (A^(n/2))^2임을 알 수 있다.

이는 멱승을 logN에 구하는 재귀함수의 형태로 구하거나 A의 2^k승에 해당하는 행렬을 이차원 배열에 저장해놓는 형태로 구해야하는 n에 대해 n의 이진수 비트에 해당하는 행렬들을 곱하는 것으로 계산할 수 있다.

 

두 경우 모두 필요한 연산의 수는 O(lgN)이며, 한 번의 행렬곱셈 연산 당 O(M^3)의 시간이 걸리므로, 한 항을 구하는데 총 O(M^3lgN)의 시간복잡도를 갖는다.

 

전체 연산을 수행할 쿼리의 수가 Q개라면 총 O(QM^3lgN)으로 문제를 해결할 수 있다.

 

 

위의 경우, 점화식이 모두 An에 관련된 형태인 선형 점화식임을 알 수 있다. 하지만 행렬을 이용한 연산을 할 경우, 선형 점화식이 아니더라도 표현할 수 있다.

 

또한, 동차 점화식이 아니더라도 표현할 수 있다.

 

 

(* 추가할 내용들은 더 추가하겠습니다.)