피보나치 수에 대한 프로그램

피보나치 수열이란?

피보나치 수열은 다음 항이 이전 두 항의 합인 수열입니다. 피보나치 수열의 처음 두 항은 0 다음에 1입니다.

The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21 ....

수학적 용어로 피보나치 수의 시퀀스 Fn은 재귀 관계로 정의됩니다.

Fn = Fn-1 + Fn-2 

어디

F0 = 0 , F1 = 1

피보나치 수열 프로그램을 작성하는 세 가지 방법에 대해 논의할 것입니다.

재귀를 사용하는 피보나치 수열

반복 방법을 사용한 피보나치 수열

행렬 지수를 사용한 피보나치 수열

(1) 재귀 방법:

직접 재귀 구현 수학적 반복 관계인 간단한 방법이 위에 나와 있습니다.

//pseudo code 
RFib(n)
{
  if n=0 return 0;
    else if n=1 return 1;
         else return (RFib(n-1)+RFib(n-2));
}

시간 복잡도: T(n) = T(n-1) + T(n-2) 지수적입니다.
추가 공간: 함수 호출 스택 크기를 고려하면 O(n), 그렇지 않으면 O(1).

Run Replit

(2) 반복 방법:

다음 피보나치 수를 직렬로 얻는 데 필요한 전부이기 때문에 이전 두 수만 저장하여 재귀 방법에서 사용되는 공간을 최적화할 수 있습니다.

//pseudo code 
IFib(n)
if n=0 return 0;
   else if n=1 return 1;
        else {   a <= 0; b<=1;
            for(i=2 to n) do
            { temp <= b;
              b<= a+b;
              a <= temp;
            }
return b;

시간 복잡도: O(n)
추가 공간: O(1)

Run Replit

(3) 행렬 거듭제곱:

n > 1로 설정





시간복잡도 : O(log(n))
추가 공간 : 함수 호출 스택 크기를 고려하면 O(log(n)), 그렇지 않으면 O(1).

Run Replit

읽어 주셔서 감사합니다