행렬과 분할정복 기반의 피보나치 수 알고리즘

기존 피보나치의 수열을 구하는 알고리즘은 다음과 같다

int Fibonacci(int n)
{
if(n==0)
return 0;
if(n==1 || n==2)
return 1;
return Fibonacci(n-1) + Fibonacci(n-2);
}

하지만 이 알고리즘은 점점 재귀함수를 호출하는 횟수가 2배씩 늘어서

시간복잡도가 이기 때문에 매우 비효율적이다.

하지만 행렬과 분할정복 기법을 활용하면 수준으로 알고리즘을 개선할 수 있다.

우선 n번째 피보나치 수를  이라 하고 아래와 같은 2x2 정사각형 행렬을 만들 수 있다.

이 정사각행렬을 n번 제곱하면 다음과 같은 등식을 유도할 수 있다.

위의 행렬식을 이용해서 알고리즘을 만들면 의 알고리즘을 구현할 수 있지만 

을 이용하면 좀 더 빠른 알고리즘을 설계할 수 있다.

위 식을 활용하여 n이 1이 될때까지 반으로 계속 분할한 다음 다시 합쳐서 원래 구하려던

 원래의  을 구하여 n번째 피보나치 수열인 을 구할 수 있다.

저 위의 식은 n이 짝수일 때 적용되고 n이 홀수일 경우엔 n을 2로 나누면서 1이 버려지기 때문에 

이렇게  을 한번 곱해야 한다.

이 알고리즘을 기반으로 c++로 구현해보았다.

#include<iostream>
typedef unsigned long ULONG; //unsigned long을 LONG으로 사용
using namespace std; 

typedef struct Matrix_2x2 //2x2 정사각행렬 구조체
{
	ULONG f[2][2];

}Matrix2x2;

Matrix2x2 mulitply(Matrix2x2 A, Matrix2x2 B)
{
	//행렬의 곱하기 함수, A와 B를 곱해서 반환
	Matrix_2x2 C;
	C.f[0][0] = A.f[0][0]*B.f[0][0] + A.f[0][1]*B.f[1][0];
	C.f[0][1] = A.f[0][0]*B.f[0][1] + A.f[0][1]*B.f[1][1];
	C.f[1][0] = A.f[1][0]*B.f[0][0] + A.f[1][1]*B.f[1][0];
	C.f[1][1] = A.f[1][0]*B.f[0][1] + A.f[1][1]*B.f[1][1];

	return C;
}
//분할정복 기법으로 구현한 피보나치 수열 구하는 함수
Matrix2x2 Matrix_Power(Matrix2x2 A, int n)
{
	
	if (n > 1) //n이 1보다 클때
	{
		//짝수일경우 반으로 나눠서 Matrix_Power 재귀 호출 
		A = Matrix_Power(A, n / 2);
		A = mulitply(A, A);// A^n = A^(n/2) * A^(n/2)

		if (n & 1) //n이 홀수일 경우
		{
			Matrix2x2  F1 = { 1,1,1,0 };
			/*행렬
			 {1,1}
			 {1,0} 을 곱하여 나누기 연산으로 버려진 1을 보완
			*/
			A = mulitply(A, F1);
		}
		
	}

	
	return A;
	
	
}

int main()
{
	int n;
	cin >> n;
	Matrix2x2  F1 = { 1,1,1,0 };
	F1 = Matrix_Power(F1, n);
	cout << n<<"번째 피보나치 수" << F1.f[0][1] << endl;
	
}