자바스크립트의 피보나치 수열

피보나치 수는 처음 두 개 이후의 모든 수는 앞의 두 수의 합이 되도록 하는 수입니다. 시리즈는 1, 1로 시작합니다. 예 -

1, 1, 2, 3, 5, 8, 13, 21, 34, ….

다음과 같이 n번째를 생성하는 프로그램을 작성할 수 있습니다 -

functionfibNaive(n) {
   if (n<= 1) return n;
   returnfibNaive(n - 1) + fibNaive(n - 2);
}

−

console.log(fibNaive(7));
console.log(fibNaive(8));
console.log(fibNaive(9));
console.log(fibNaive(4));

이것은 출력을 줄 것입니다 -

13
21
34
3

이러한 함수 호출이 실제로 어떻게 발생하는지 살펴보겠습니다 -

/**
* f(5)
* / \
* f(4) f(3)
* / \ / \
* f(3) f(2) f(2) f(1)
* / \ ..........
* f(2) f(1)..........
*/

f(5)를 호출할 때 f(2)를 거의 4번 호출하고 동일한 코드를 4번 이상 실행합니다. 이것은 하위 문제가 겹치는 경우입니다. 500에 대해 해당 기능을 실행해 보십시오. 이 모든 호출에 시간이 많이 걸리므로 멈춥니다.

다섯 번째 피보나치 수가 필요할 때 더 낮은 피보나치 수는 한 번만 필요하지만 그보다 훨씬 더 많이 계산합니다. 계산된 값을 대신 어딘가에 저장하면 이 중복 계산을 줄일 수 있습니다. 이것이 동적 프로그래밍의 핵심입니다.

한 번 계산하고 나중에 재사용합니다.

fib 함수의 암기된 구현을 살펴보겠습니다.

letfibStore = {};
functionfibDP(n) {
   if (n<= 1) return n;
if (fibStore[n]) {
   returnfibStore[n];
}
   fibStore[n] = fibDP(n - 1) + fibDP(n - 2);
   returnfibStore[n];
}

이제 우리는 이미 계산한 값을 추적하기 위해 fibStore라는 저장소를 사용하고 있습니다. 이는 과도한 중복 계산을 줄이고 기능을 효율적으로 유지합니다.

−

console.log(fibDP(7));
console.log(fibDP(8));
console.log(fibDP(9));
console.log(fibDP(4));

이것은 출력을 줄 것입니다 -

13
21
34
3

엄청난 값에 대해 테스트할 수도 있습니다.