🍋 피보나치 수열 중 n번째 항의 수를 리턴한다.

Time Complexity(시간 복잡도)

알고리즘의 로직을 코드로 구현할 때 효율적인 방법을 고민해본다.
입력값이 커짐에 따라 연산시간이 늘어날텐데, 증가하는 시간의 비율을 최소화한 알고리즘

• Big-O : 상한 점근
• Big-Ω : 하한 점근
• Big-θ : 둘의 평균
  => 시간 복잡도 최악/최선/중간(평균)의 경우
  => 최악의 경우가 발생하지 않기를 바라며 시간을 계산하는 것보다 최악의 경우도 고려하여 대비하는 것이 바람직하다.
  => Big-O 표기법을 가장 자주 사용한다: 입력값의 변화에 따라 연산을 실행할 때 연산 횟수에 비해 시간이 얼마만큼 걸리는가?

  Big-O
  1.O(1): 일정한 복잡도. 입력값이 증가하더라도 시간이 늘어나지 않는다.
  2.O(n): 선형 복잡도. 같은 비율로 증가한다.
  3.O(log n): 로그 복잡도. BST, up & down게임. 노드를 이동할 때마다 경우의 수가 절반으로 줄어든다.
  4.O(n2): 2차 복잡도. n의 제곱수의 비율로 증가
  5.O(2n): 기하급수적 복잡도. Big-O중 가장 느린 시간 복잡도. 재귀로 구현하는 피보나치 수열

메모이제이션(memoization)

컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.
피보나치 수열을 구하는 가장 단순한 방법은 다음과 같다.

fib(n) {
   if n is 1 or 2, return 1;
   return fib(n-1) + fib(n-2);
}

이때 fib 함수가 재귀적으로 실행되면서 같은 인자값에 대해서 계속해서 반복되므로, 전체 실행시간은 Ω(1.6n)이다. 그러나 fib(n)의 값을 계산하자마자 저장하면(memoize), 실행시간을 Θ(n)으로 줄일 수 있다.

function fib(n) {
   if(memo[n] !== undefined) return memo[n]
   	memo[n] = fib(n-1) + fib(n-2)
   	return memo[n];
   
  return fib(n);
}