[Algorithm] DP - 피보나치 수열

[Cheolsker]

피보나치 수열 문제를 3가지 방식으로 풀이하고 성능 비교

조건

input 갯수를 아래와 같이 전달
const inputs = [1, 10, 30, 50, 100, 1000, 5000, 8500, 10000, 100000];

3가지 풀이

1. 일반적인 재귀함수로 풀이
2. DP 하향식, 메모이제이션으로 풀이
3. DP 상향식, 타뷸레이션으로 풀이

성능 비교

 /**
     * <fibonacci1>
     *
     * case 1 | length-1: 0.036ms
     * case 2 | length-10: 0.008ms
     * case 3 | length-30: 7.892ms
     *
     * 30개를 넘으면, 시간 초과
     *
     */
    // const result = fibonacci1(inputs[i]);

    /**
     * <fibonacci2>
     *
     * case 1 | length-1: 0.038ms
     * case 2 | length-10: 0.007ms
     * case 3 | length-30: 0.003ms
     * case 4 | length-50: 0.018ms
     * case 5 | length-100: 0.007ms
     * case 6 | length-1000: 0.057ms
     * case 7 | length-5000: 0.245ms
     * case 8 | length-8500: 4.097ms
     *
     * 갯수가 8500개를 넘어가면 스택오버플로우 발생!
     */
    // const result = fibonacci2(input);

    /**
     * <fibonacci3>
     *
     * case 1 | length-1: 0.064ms
     * case 2 | length-10: 0.014ms
     * case 3 | length-30: 0.02ms
     * case 4 | length-50: 0.019ms
     * case 5 | length-100: 0.019ms
     * case 6 | length-1000: 0.049ms
     * case 7 | length-5000: 0.277ms
     * case 8 | length-8500: 0.652ms
     * case 9 | length-10000: 1.067ms
     * case 10 | length-100000: 197.021ms
     *
     * fibonacci2에 비해 전반적으로 성능이 좋음
     * fibonacci2는 재귀함수를 사용하므로, 특정 input 갯수에서 스택오버플로우 발생
     * fibonacci3는 테이블 길이만 충분하다면, 로직을 수행함
     */