[JS 스터디 1기] - fibonacci 함수 구현 코드

// fibonacci 함수 구현

// 시간 복잡도: O(n)
// 공간 복잡도: O(1)
function fibonacciIterative(n) {
  let a = 0;
  let b = 1;
  for (let i = 0; i < n; i += 1) {
    [a, b] = [b, a + b]; // 디스트럭쳐링 할당
  }
  return a;
}

// 시간 복잡도: O(2^n)
// 공간 복잡도: O(1), 재귀 호출 스택 고려 -> O(n)
function fibonacciRecursive01(n) {
  if (n === 0) return 0;
  else if (n === 1) return 1;
  return fibonacciRecursive01(n - 1) + fibonacciRecursive01(n - 2);
}

// 시간 복잡도: O(n)
// 공간 복잡도: O(n)
const cache = Array(100);
function fibonacciRecursive02(n) {
  let result;
  if (cache[n]) return cache[n];
  if (n === 0) result = 0;
  else if (n === 1) result = 1;
  else result = fibonacciRecursive02(n - 1) + fibonacciRecursive02(n - 2);
  cache[n] = result;
  return result;
}

console.log(fibonacciIterative(10));
console.log(fibonacciRecursive01(10));
console.log(fibonacciRecursive02(10));