Fibonacci 수열을 구하는 효율적인 알고리즘 O(n)으로 문제풀기
첫번째.
function fibonacci(n){
let array=[0,1]; // 바로 직전의 두 피보나치수의 합이므로 처음 두개는 정의해주어야한다.
const aux= (n) => {
if(array[n]!===undefined){ // n번째 배열이 존재하는 경우
return array[n] // n번째 배열 호출
}
array[n] = aux(n-1)+aux(n-2); //재귀함수로 n번째 피보나치 정의하기
return array[n]
}
return aux(n)
};
두번째.
function fibonacci(n){
let sqrt_5 = 5 ** (1 / 2);
let ans = 1 / sqrt_5 * ( ((1 + sqrt_5) / 2 ) ** n -((1 - sqrt_5) /2) ** n);
return parseInt(ans)
}
두번째 방법은 사실 수학공식을 사용하는 것이라, 코딩구조를 볼 것은 없다..😅