프로그래밍/자료구조 && 알고리즘
[알고리즘] 피보나치 수열의 시간복잡도
코드몬스터
2024. 7. 24. 23:21
728x90
기존 알고리즘
- O(2^n)
- 매 번 함수가 호출 될 때마다 또 두 번씩 호출 된다.
F(n, r) {
if (n <= 0) return 0;
else if (n == 1) return r[n] = 1;
return r[n] = F(n-1, r) + F(n-2, r);
}
기존 알고리즘 + 메모이제이션
- O(n)
- 메모이제이션을 통해 n을 두 번 호출 안하게 된다.
F(n, r) {
if (n <= 0) return 0;
else if (n == 1) return r[n] = 1;
⭐ else if (r[n] > 0) return r[n]; ⭐
return r[n] = F(n-1, r) + F(n-2, r);
}
변형된 피보나치 수열 풀이코드
- O(n2^n)으로 계산은 틀렸다.
- 2^n을 n번 반복하는 것으로 때문에 착각할 수 있다.
- allF은 1부터 n까지의 모든 피보나치 수를 계산하고 출력
- F(1): O(2^1)
- F(2): O(2^2)
- F(3): O(2^3)
- ...
- F(n): O(2^n)
- O(2^1 + 2^2 + 2^3 + ... + 2^n-1 + 2^n)
= 2^n - 2 + 2^n
= 2 * 2^n - 2
= 2^n (상수는 모두 제외)
allF(n) {
for (i=1 to n) print F(i);
}
F(n) {
if (n <= 0) return 0;
else if (n == 1) return 1;
return F(n-1) + F(n-2);
}
메모이제이션
F(5, r) 풀기
- ⭐ 배열의 초기 모든 값은 0 이다. ⭐
int r[6] = {0, 0, 0, 0, 0, 0}; // 초기화된 배열
int result = F(5, r); // 피보나치 수열의 5번째 값을 계산
- 5는 0보다 크기 때문에 처음 if문은 지나간다.
- 5는 1과 같지 않기 때문에 처음 else-if문을 지나간다.
- r[5]는 0이기 때문에 두 번째 else-if문을 지나간다.
=> 처음 배열의 모든 값은 0이다. - 그럼 return으로 F(4, r) + F(3, r)을 반환한다.
이렇게 계속 반복하면서 F(5), F(4), F(3), F(2), F(1), F(0)을 만나는 순간 !!
=> 두 갈래로 나누면서 계속 내려가겠지만 한쪽에서 분명 F(1)과 F(0)을 만나게 된다.
역으로 값을 하나씩 더하면서 배열의 값을 수정한다.
=> F(0, r)=0 , F(1, r)=1, F(2, r)=1, F(3, r)=2, ...
=> int r[6] = {0, 1, 1, 2 .... }
즉, 한 쪽에서 계산하고 배열에 값을 저장해 놓으면
다른 한 쪽에서는 다시 나눌 필요없이 배열에서 값을 가져와서 더하면 끝!
=> " 다시 나눌 필요없이"는 F(n-1, r) + F(n-2, r)를 의미
=> 우리는 해당 F(n-1, r) 의 값을 배열에서 바로 알 수 있다.
따라서 O(2^n)이 아닌 O(n) 복잡도로 계산이 끝난다.
참고사이트
https://www.youtube.com/watch?v=VcCkPrGaKrs