티스토리 뷰

알고리즘

[Cache] fibonacci?

seunggabi 승가비 2018. 9. 7. 20:07

[Cache] fibonacci?


피보나치 함수는 일반적으로 시간복잡도가 O(2^N) 이다. 

정확하게 하면 O(1.6^N) 이다. 이렇게 지수승 시간복잡도는 매우 큰 값이므로 N이 커지면 구하기 어렵다. 

그래서 fibonacci 함수를 만들때 시간복잡도를 선형으로 줄이기 위해 

cache로 기존 호출했던 함수 값을 재사용해서 O(N)을 사용하도록 한다.


// fibonacci
// cache 사용의 중요성을 알게 해주는 예제
// cache를 사용하지 않는다면, fibonacci 의 시간복잡도는 O(2^N) 이다.
// 정확하게는 O(1.6^N) 이다. 왜냐하면, 양쪽이 동일한 트리모양이 아니라 한쪽만 뻗어나가는 트리이므로.
// cache를 사용하면 O(N)으로 해결할 수 있다.
// this-> pointer 이므로.
// 공간복잡도는 O(N) 이다.

#include <iostream>
using namespace std;

#define SIZE 1000000

class Fibonacci {
private:
int cache[SIZE];
public:
int get(int n) {
if(cache[n]) return cache[n];
if(n < 2) return cache[n] = n;
if(n < 0) return -1;

return cache[n] = this->get(n-1) + this->get(n-2);
}
};

int main() {
Fibonacci fibonacci;

cout << fibonacci.get(20) << endl;
return 0;
}


댓글
댓글쓰기 폼