[Cache] fibonacci?

[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;
}