fibonacci

피보나치 수열은 아래와 같은 특징을 가지고있다 

• 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의 합으로 정의합니다.
• 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

---

• 재귀 형태로 호출시 아래와 같이 트리 구조로 호출이 되면 O(n^2)  형태로 표현이 된다 

 

 

• 위 그림 처럼 사용시 불필요한 메모리를 차지한다 
• 아래 그림처럼 불 필요 한걸 제거한다면 O(N) 형태로 아래와 같이 코드 작성이 가능하다 

function _fibonacci(n, memo) {
    if ((memo[n] != 0) && (memo[n] != undefined)){ // 기록한거 사용 
        return memo[n]; 
    }
    else    // 기록이 없을시 계산후 저장 
    { 
        if(n == 1 || n==2){
            memo[n] = 1;
        }else{
            memo[n]= _fibonacci(n-1, memo) + _fibonacci(n-2, memo);
        }
         return memo[n];  
    }
}

function fibonacci(n) {
    var arr = new Array(n+1);
    return _fibonacci(n,arr);
}