[Algorithm] 피보나치 수열과 시간복잡도

피보나치 수열의 n번째 수를 구하는 문제.

재귀(Recursion)를 이용해 아래로 내려가는 Top-Down 방법과 0번째 부터 n 번째 까지 더해가며 구하는 Bottop-Up 방법을 사용했다. 재귀를 사용하여 풀었을 때 답은 구해졌지만, 실행 시간이 오래 걸려서 테스트를 하나 통과하지 못했다. 요구 시간은 0.1 이었고, 재귀를 이용한 풀이는 0.368초가 걸렸다. 그 이유는 시간복잡도가 재귀를 이용했을 때는 O(2^2/n), 반복문을 이용했을 때는 O(n)이 나오기 때문이다.

재귀를 이용한 피보나치 수열의 시간복잡도

T(n) : fib(n)을 계산하기 위하여 fib함수를 호출하는 횟수 (재귀 트리 상의 노드의 개수)
T(0)=1 (0일 수도 있다)
T(1)=1
T(n)=T(n-1) + T(n-2) +1 for(n>=2)

2^1 x T(n-2) => T(n-1)이 T(n-2)보다 크기 때문에 T(n-1)+T(n-2) > T(n-2)+T(n-2)
2^2 x T(n-4)
2^3 x T(n-6)
...
2^n/2 x T(0)
= 2^n/2

재귀를 이용한 피보나치 수열

var nthFibonacci_Rec = function (n) {
  // TODO: implement me!

  //////// By using recursion
   var storage = [0,1,1];
   if(n === 0){
     return storage[n];
   }else if(n === 1){
     return storage[n];
   }else{
     return nthFibonacci_Rec(n-1)+nthFibonacci_Rec(n-2);
   }
};

반복문을 이용한 피보나치 수열

var nthFinobacci_BottomUp = function (n) {
  var storage = [0,1];

  for(let i=2 ; i<=n ; i++){
    storage[i] = storage[i-1] +storage[i-2];
  }

  return storage[n];
}