피보나치 수열

피보나치의 0번째 수가 0, 1번째 수가 1이다. 그 다음 2번째 수부터는 바로 직전의 두 피보나치 수의 합으로 정의된다. 따라서 0,1,1,2,3,5,8,13,21,....이런 형태로 이어진다. 피보나치 수열의 n번째 항의 수를 구하는 방법은 여러가지이나, 각각이 모두 효율적인 것은 아니다.

재귀함수

시간복잡도가 지수 함수인 재귀 알고리즘

function fibonacci(n){
  if(n<=1)
  {
    return n
  }
  return fibonaci(n-1)+fibonacci(n-2);
}

한번 실행할때마다 2번실행되어 결국 트리구조를 이루게 되고, n번 실행하면 2의 n거듭제곱만큼 함수를 호출하게 된다. 따라서 시간복잡도는 시간복잡도는 대략 O(2^n)라고 할 수 있다.

동적프로그래밍

시간복잡도가 선형인 재귀 알고리즘

동적 프로그래밍은 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있을때 프로그램의 속도를 비약적으로 향상시킬 수 있다. 피보나치 수열은 대표적인 동적 프로그램의 예시인데, f(n)의 값을 구하기 위해 그보다 작은 f(n-1)과 f(n-2)를 호출해야하기 때문이다.

동적 프로그래밍의 핵심은 한번 구한 값을 저장하여 이 값이 다시 필요할때, 함수를 다시 호출하지 않고, 저장된 값을 불러오는 것이다. 따라서 첫번째 사례에서 매번 새롭게 함수가 호출되되어 시간이 기하급수적으로 늘어났던 것과 다르게 시간을 단축할 수 있게 되는 것이다.

let fib = [0,1]
function fibonacci(n){
  if(n<=1){
    return fib[n]
  }
  fib[n] = fibonacci(n-1) + fibonacci(n-2);
  return fib[n];
}

이 경우는 시간복잡도가 O(n)이다. 이러한 동적프로그래밍 기법을 메모이제이션이라 한다. 여기서 fib는 전역변수로 글로벌 스코프에 저장되어 있으므로 함수를 여러번 호출할때 유용하다.