피보나치 수

개요

F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2 (n >= 2)
문제 : N번째 피보나치 수를 구하는 문제
작은 문제 : N-1번째 피보나치 수를 구하는 문제, N-2번째 피보니치 수를 구하는 문제

매커니즘

• 문제: N번째 피보나치 수를 구하는 문제
• 작은 문제: N-1번째 피보나치 수를 구하는 문제, N-2번째 피보나치 수를 구하는 문제
• 문제: N-1번째 피보나치 수를 구하는 문제
• 작은 문제: N-2번째 피보나치 수를 구하는 문제, N-3번째 피보나치 수를 구하는 문제
• 문제: N-2번째 피보나치 수를 구하는 문제
• 작은 문제: N-3번째 피보나치 수를 구하는 문제, N-4번째 피보나치 수를 구하는 문제

코드

피보나치

int memo[100];
int fibonacci(int n) {
	return n;
} else {
    return fibonacci(n-1) + fibonacci(n-2);
  	}
}

시간복잡도

피보나치수 함수를 하나 호출 할때마다 구조상 두개의 함수를 재귀로 다시 호출하고 있다 따라서, 함수의 깊이가 N이라고 하면 2의 N제곱 만큼의 복잡도를 가지게 되므로
시간복잡도 : 2^N 이라고 할 수 있다.

Memoization을 활용한 피보나치수

int memo[100];
int fibonacci(int n) {
	return n;
} else {
	if (memo[n]) {
    	return memo[n];
    }
    memo[n] = fibonacci(n-1) + fibonacci(n-2);
    return memo[n];
  	}
}

시간복잡도

다이나믹프로그래밍으로 푸는 모든 문제들은 1번씩 풀게 되어있다.
문제의 개수 X 문제 1개를 푸는 시간 = 함수의 시간 복잡도
따라서 시간복잡도 : O(N)이다.