DP 메모이제이션: 피보나치의 중복 호출 줄이기

피보나치 원본 비교: 실행시간보다 호출과 저장을 셉니다

첨부 dev/fibonacci2.mjs는 단순 재귀 fibonacci1(n)과 메모이제이션 fibonacci2(n, memo)를 같은 파일에서 비교합니다. 두 함수의 목표는 같은 숫자 F(n)입니다. 메모이제이션이 줄이는 것은 정답 자체가 아니라 이미 계산한 상태 아래의 반복 호출입니다. 앞에서 배운 저장 원리를 실제 호출 수에 연결해 보겠습니다.

원본은 n – 2를 먼저 계산합니다

원본의 식은 fibonacci(n - 2) + fibonacci(n - 1)입니다. 따라서 F(5)를 요청하면 왼쪽 F(3)부터 내려갑니다. F(3)은 F(1)과 F(2)를 구해 2를 저장하고, 이어 오른쪽 F(4)는 저장된 F(2)=1과 F(3)=2를 꺼내 3을 저장합니다. 마지막으로 F(5)=2+3=5입니다. 앞선 개념 설명의 큰 하위 상태부터 따라가는 순서와 달라도 정답은 같습니다.

여기서 전체 호출에는 첫 호출과 F(0)·F(1) 기저 호출도 포함합니다. 저장된 답을 꺼내는 호출도 함수에 들어간 횟수에는 포함하지만, 두 하위 상태를 다시 풀지는 않습니다. 기저 조건은 저장소 검사보다 먼저 반환하므로 위의 적중 횟수에는 F(0)·F(1)을 넣지 않습니다. F(6)에서는 두 방식의 전체 호출이 각각 25회와 11회가 됩니다.

memo의 수명과 입력 계약도 비교합니다

원본의 두 번째 함수는 호출자가 {}를 전달하고, 그 객체를 재귀 호출들이 공유합니다. memo[n] == null은 값이 null 또는 undefined일 때 계산하겠다는 뜻입니다. if (!memo[n])처럼 0을 미저장 상태로 취급하는 검사와 다릅니다. 다만 호출자가 잘못 채운 객체도 그대로 신뢰하고, n≥2에서 저장소를 생략하면 오류가 납니다. 학습용 독립 예제는 매 비교마다 내부 Map을 새로 만들고 has로 존재를 검사합니다.

원본은 ==를 써서 문자열 "1"도 기저 조건을 통과하며 그 문자열 자체를 반환할 수 있습니다. 음수나 소수는 정상적인 종료를 보장하지 않습니다. 아래 비교 함수는 숫자형 정수만 받고, 단순 재귀도 함께 실행하므로 0~20으로 제한합니다. 기존 본문의 메모이제이션 전용 예제 0~78 범위와는 목적이 다른 제한입니다. 이 범위를 넘는 비교 입력은 오류로 알립니다.

원본 두 함수는 F(n) 숫자 하나를 반환합니다. 아래의 내부 함수도 숫자를 반환하지만, 바깥 compareFibonacci(n)는 두 답과 호출 수·적중 수·저장 순서를 담은 객체를 반환합니다. 계산 과정이 보이도록 추가한 반환 계약이며, 소요 시간을 반환하는 함수는 아닙니다.

밀리초 차이는 복잡도의 증명이 아닙니다

원본은 n=40에서 두 답을 출력하고 Date의 차이로 시간을 잽니다. 두 답은 모두 102334155이지만, 밀리초 값은 실행 환경마다 달라집니다. 원본의 측정 구간에는 결과를 출력하는 console.log도 들어갑니다. 한 번의 측정에는 출력 비용·실행 준비·다른 작업의 영향이 섞이므로 고정된 시간이나 배속을 학습 결론으로 쓰지 않습니다. 아래에서는 작은 n의 호출 수를 셉니다.

단순 재귀의 호출 수는 빠르게 늘며 O(2ⁿ)은 그 상한입니다. 메모이제이션은 각 상태를 한 번 계산하므로 숫자 덧셈과 저장소 접근을 상수 비용으로 보는 조건에서 O(n) 시간입니다. 둘 다 가장 깊은 호출 경로의 스택은 O(n)이고, 메모이제이션에는 O(n) 저장소도 필요합니다. 아래 비교 도구는 두 실행과 관찰 기록을 모두 포함하므로 도구 전체가 O(n)이라고 해석하면 안 됩니다. Number 정수 범위는 ECMAScript의 안전한 정수 규칙과 별도로 확인해야 합니다.

function compareFibonacci(n) {
  if (!Number.isInteger(n) || n < 0 || n > 20) {
    throw new RangeError('비교 예제는 정수 0~20만 받습니다.');
  }
  let plainCalls = 0;
  let memoCalls = 0;
  let memoHits = 0;
  const computedStates = [];
  const cache = new Map();

  function plain(k) {
    plainCalls++;
    if (k === 0 || k === 1) return k;
    return plain(k - 2) + plain(k - 1);
  }

  function memo(k) {
    memoCalls++;
    if (k === 0 || k === 1) return k;
    if (cache.has(k)) {
      memoHits++;
      return cache.get(k);
    }
    const value = memo(k - 2) + memo(k - 1);
    cache.set(k, value);
    computedStates.push(k);
    return value;
  }

  const plainValue = plain(n);
  const memoValue = memo(n);
  return { n, plainValue, memoValue, plainCalls, memoCalls, memoHits, computedStates };
}

console.log(JSON.stringify(compareFibonacci(5)));
console.log(JSON.stringify(compareFibonacci(6)));

node supplement-fibonacci-call-counts.js

{"n":5,"plainValue":5,"memoValue":5,"plainCalls":15,"memoCalls":9,"memoHits":2,"computedStates":[2,3,4,5]}
{"n":6,"plainValue":8,"memoValue":8,"plainCalls":25,"memoCalls":11,"memoHits":3,"computedStates":[2,3,4,5,6]}