JavaScript 알고리즘: 피보나치 수열 풀기(LeetCode)

일반적으로 표시 되는 피보나치 수열은 피보나치 수열F(n) 이라고 하는 수열을 형성하며 각 수는 및 에서 시작하는 앞선 두 수의 합입니다 . 다음 정수 시퀀스의 숫자 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ……..01

그건

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

예 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

• 0 <= n <= 30

이 문제를 해결하기 위한 몇 가지 옵션이 있습니다. 재귀 접근 방식.

재귀 접근법

직접 재귀 구현 수학 반복 관계인 간단한 방법입니다. 기하 급수적 인 시간 복잡도 : O(2^N) 및 공간 복잡성 : O(N) 이 필요하기 때문에이 문제를 해결하는 가장 느린 방법 입니다.

메모이제이션을 이용한 동적 프로그래밍(Top down approach)

지금까지 계산한 피보나치 수를 저장하면 재귀적으로 반복되는 작업을 피할 수 있습니다. 모든 값을 맵에 저장하기만 하면 됩니다. 시간 복잡도 : O(N) 및 공간 복잡도 : O(N) .

반복 접근

이미 계산된 피보나치 값을 사용하여 모든 하위 문제를 해결하고 N 요소에 대한 답을 반환하는 반복. 시간 복잡도 : O(N) 및 공간 복잡도 : O(N) .

반복 접근 방식( 공간 최적화)

이전 두 개의 숫자를 저장하는 반복 접근 방식을 최적화할 수 있습니다. 그 이유는 다음 피보나치 수를 직렬로 얻는 데 필요한 전부이기 때문입니다. 시간 복잡도 : O(N) 및 공간 복잡도 : O(1) .

행렬 지수화 접근법

행렬 지수를 사용 하여 결과 행렬의 (0, 0) 에 있는 요소에서 피보나치 수를 가져옵니다 . 이를 위해 피보나치 수열에 대한 행렬 방정식을 사용하여 N 번째 피보나치 수를 찾을 수 있습니다.

이 공식은 어떻게 작동합니까? Wiki 에서 볼 수 있습니다.

이 솔루션은 시간 복잡도 : O(logN) 및 공간 복잡도 : O(logN) 을 갖 습니다.

수학적 접근법

다음 을 사용할 수 있습니다 golden ratio forumula.

다음 은 피보나치 수열과 황금 비율이 작동하는 방식에 대해 자세히 알아볼 수 있는 링크 입니다.

이 솔루션은 시간 복잡도 : O(logN) 및 공간 복잡도 : O(1) 을 갖 습니다.

또한 때로는 주어진 N에 대한 값을 반환하는 것이 아니라 주어진 N까지 피보나치 요소의 배열을 반환해야 합니다.

예시:

Input: n = 7
Output: [0, 1, 1, 2, 3, 5, 8, 13]

거의 변경하지 않고 메모이제이션을 사용하는 동적 프로그래밍 :

우리는 피보나치 문제를 해결하기 위해 다양한 옵션을 고려했습니다. 이해하기 가장 어려운 것은 행렬 지수화이지만 일반적으로 이전 4가지 방법에 대한 지식이면 인터뷰에 충분합니다.

도움이 되었기를 바랍니다!

읽어 주셔서 감사합니다! 곧 봐요.

PlainEnglish.io 에 더 많은 내용이 있습니다 . 무료 주간 뉴스레터 를 신청 하십시오. Twitter , LinkedIn , YouTube 및 Discord 에서 팔로우하세요 . 그로스 해킹에 관심이 있으십니까? 회로 를 확인하십시오 .