[알고리즘] 피보나치 수 구하기

피보나치 수열은 다음 조건을 만족하는 수열이다.

$F_0=1, F_1=1, F_n=F_{n-1}+F_{n-2} \ (n \gt 2)$

$1,1,2,3,5,8,13...$

(경우에 따라서 $F_0=0$이 되기도 함)

 

위 식을 사용해서 구하면 시간 복잡도가 $ O(N) $이기 때문에 $N <100,000,000$ 정도까지는 구하겠지만 그 이상되는 수는 구하기가 힘들다.

이를 최적화하여 빠르게 구해보자!

 

다음과 같은 행렬이 있다고 하자

$A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end {pmatrix}$

 

이 행렬을 거듭제곱해보자

$A^2 = \begin {pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 2 & 1 \\ 1 & 1 \end {pmatrix}$

$A^3 = \begin {pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 3 & 2 \\ 2 & 1 \end {pmatrix}$

$A^4 =\begin {pmatrix} 3 & 2 \\ 2 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}= \begin{pmatrix} 5 & 3 \\ 3 & 2 \end {pmatrix}$

 

이를 일반화해보면

$A^n = \begin {pmatrix} F_n & F_{n-1} \\ F_{n-1} & F_{n-2} \end {pmatrix}$

가 된다.

 

따라서 우리는 행렬 $A$를 $n$제곱한 후 $0$행, $0$열의 수를 얻으면 된다.

 

거듭제곱 알고리즘은 $O(\log N)$임이 알려져 있고 행렬 연산은 $O(2^3)$이므로 피보나치 수를 구하는데 $O(\log N)$시간 내에 구할 수 있다.

(점화식 특성상 Berlekamp-Massey 알고리즘으로도 구할 수 있다.)