정의

\[a_n = a_{n-1} + a_{n-2}\ (n > 1)\] \[a_1 = 1\] \[a_0 = 1\]

구현

재귀 (recursion)

시간복잡도

\[O(2^n)\]

구조도

graph BT;
    0,0((a4))
    1,0((a3))
    1,1((a2))
    2,0((a2))
    2,1((a1))
    2,2((a1))
    2,3((a0))
    3,0((a1))
    3,1((a0))

    1,0-->0,0
    1,1-->0,0
    2,0-->1,0
    2,1-->1,0
    2,2-->1,1
    2,3-->1,1
    3,0-->2,0
    3,1-->2,0

관련 문제 (BOJ)

번호	제목	n	연산 횟수
10870	피보나치 수 5	20	220 ≒ 106 <= 108

동적 계획법 (Dynamic Programming)

시간복잡도

\[O(n)\]

구조도

관련 문제 (BOJ)

번호	제목	n	연산 횟수	변형
2747	피보나치 수	45	45 <= 108
2748	피보나치 수 2	90	90 <= 108
10826	피보나치 수 4	10000	104 <= 108

<a href=https://www.acmicpc.net/problem/2747></a>

번호	제목	n	연산 횟수
2747	<a href=https://www.acmicpc.net/problem/2747>피보나치 수</a>	45

분할 정복 (Divide and Conquer)

시간복잡도

\(O(logn)\)

수식

\[\begin{bmatrix}1 & 1\\1 & 0\end{bmatrix} \begin{bmatrix}a_1\\a_0\end{bmatrix} = \begin{bmatrix}a_2\\a_1\end{bmatrix}\] \[\begin{bmatrix}1 & 1\\1 & 0\end{bmatrix}^n \begin{bmatrix}a_1\\a_0\end{bmatrix} = \begin{bmatrix}a_{n+1}\\a_n\end{bmatrix}\] \[\begin{bmatrix}1 & 1\\1 & 0\end{bmatrix}^n \begin{bmatrix}1\\0\end{bmatrix} = \begin{bmatrix}a_{n+1}\\a_n\end{bmatrix}\]

BOJ