Fibonacci 수열을 구하는 효율적인 알고리즘

Purple·2021년 10월 9일
0

TIL

목록 보기
28/73

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)
}

두번째 방법은 사실 수학공식을 사용하는 것이라, 코딩구조를 볼 것은 없다..😅

profile
다시 보면, 더 많은 것들이 보인다.

0개의 댓글