피보나치 (재귀, memoize, bottom-up)

피보나치

• 출처 : CS dojo - What Is Dynamic Programming and How To Use It

일반적인 재귀 풀이

function fibonacci(n){
  if (n === 0)
    return 0;
  if (n === 1 || n === 2)
    return 1;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

// 시간 측정 결과 88ms
console.time('recursion');
fibonacci(35);
console.timeEnd('recursion');

// 1518ms
console.time('recursion');
fibonacci(41);
console.timeEnd('recursion');

// 10490ms
fibonacci(45);

memoize

function fibonacciMemo(n, memo = []){
  if(memo[n]) return memo[n];
  
  let result;
  if(n === 2 || n === 1){
    result = 1;
  }else{
    result = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
  }
  memo[n] = result;
  return result;
}

// 0.09 ms
console.time('memoize');
fibonacciMemo(35);
console.timeEnd('memoize');

// 0.10 ms
console.time('memoize');
fibonacciMemo(41);
console.timeEnd('memoize');

// 2.52 ms
fibonacciMemo(5000);

// Uncaught RangeError: Maximum call stack size exceeded
fibonacciMemo(10000);

fibonacci_bottom_up

function fiboBottomUp(n){
  if(n === 1 || n === 2) return 1;
  const bottomUp = [];
  bottomUp[1] = 1;
  bottomUp[2] = 1;
  for(let i = 3; i <= n; i++){
  	bottomUp[i] = bottomUp[i - 1] + bottomUp[i - 2];
  }
  return bottomUp[n];
}

// 0.08 ms
console.time('bottom-up');
fiboBottomUp(35);
console.timeEnd('bottom-up');

// 0.09 ms
fiboBottomUp(100);

// 0.49 ms
fiboBottomUp(5000);

// 1.74 ms
fiboBottomUp(10000);

궁금증, 더 공부해볼 것들

• dynamic programming 풀이법에 대해 공부하기 위해서 선행한 풀이법
  - dynamic programming의 이름이 이상하다고 느꼈는데 위키피디아, 제로초님 블로그에 이름의 유래에 대한 설명이 있어서 직성이 조금 풀렸다.
  • 위키피디아 - 동적 계획법, zerocho - 동적 프로그래밍
• bottom-up 방식이 더 빠른 이유는 call stack을 생성하지 않기 때문인지?