피보나치 수

피보나치 수를 구하는 알고리즘은 여러가지다.

그 중 대표적으로 

1. 재귀를 통한 단순 구현 (Top-down) [ O(2^(N/2)) ]

2. 반복문을 통한 단순 구현 || 메모이제이션 (Bottom-up) [ O(N) ]

2. 1 피사노의 주기

3. 행렬을 통한 분할 정복 [ O(logN) ]

4. 일반항을 통한 계산 [ O(logN) ]

N이 엄청 큰 경우

1, 2번 방법으론 시간내 풀 수 없으니 시간 복잡도가 O(logN)인 방법으로 해결해야한다.

3번, 행렬을 통한 분할 정복을 보자.

피보나치 식을 행렬로 표현하면 위와 같이 표현이 가능하다.

증명은 (여기)에서 볼 수 있다.

 

N번째 피보나치 수를 구하기 위해서 제곱을 하면서 찾아가게 되는데

어떤 수의 제곱수 X^n = X^(n/2) * X^(n/2)로 표현할 수 있다.

 

예를 들어

2^10을 구하기 위해서 단순 반복이나 재귀를 사용할 경우,

2^10 = 2^9 *2 ,  2^9 = 2^8 * 2 ........ 2^2 = 2^1 * 2^1

이렇게 10번의 계산과정이 필요하다.

 

하지만 분할 정복을 이용하게 될 경우

2^10 = 2^5 * 2^5 // 2^5 = 2^2 * 2^2 * 2^1 //  2^2 = 2^1 * 2^1

이렇게 3번의 과정으로 끝낼 수 있다.