피보나치 수열(Fibonacci Sequence)

피보나치 수열(Fibonacci Sequence)

---

피보나치 수열(Fibonacci Sequence)은 각 항이 이전 두 항의 합으로 정의되는 수열입니다.

 

수열의 초기값은 다음과 같습니다.

F(0) = 0, F(1) = 1

 

그리고 다음 항은 이런식으로 계산됩니다.

F(n) = F(n -1) + F(n - 2) (n ≥ 2)

 

재귀(Recursion) 방식 코드 구현 예제(Java 구현)

class FibonacciSequences {
    public int fibonaccisequence(int n) {
        if (n == 0) {
            return 0;
        }
        else if (n == 1) {
            return 1;
        }
        return fibonaccisequence(n - 1) + fibonaccisequence(n - 2);
    }
}
public class FibonacciSequence {
    public static void main(String[] args) {
        FibonacciSequences fibonacciSequences = new FibonacciSequences();
        int F = 7;

        int location = fibonacciSequences.fibonaccisequence(F);

        System.out.println("result : " + location);
    }
}

 

재귀 방식 피보나치 수열의 특징

구현이 매우 간단하여 작성하기 쉽고 타인이 보기에 이해기 쉽지만 매우 큰 단점으로 비효율적이라 느립니다. 예를 들면 F(5)를 얻기 위해서는 F(4)와 F(3)이 필요하고 F(3)은 F(2)와 F(1)이 필요합니다. 이런식으로 계산을 중복하여 호출하기 때문에 비효율적입니다. 즉 알고리즘을 계싼하기 위해서는 n이 2 증가할 때마다 항의 개수는 배로 늘어납니다. 

 

재귀 방식 피보나치 수열의 시간 복잡도

n이 2 증가할 때마다 항의 개수가 2배로 늘어나므로

• 시간 복잡도 : O(2^n) (지수적 증가)

 

반복(Iterative) 방식 코드 구현 예제 (Java 구현)

class FibonacciSequences {
    // 반복문 방식
    public int Iterative(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        }
        int prev = 0;  // 이전 피보나치 수
        int curr = 1;  // 현재 피보나치 수
        for (int i = 2; i <= n; i++) {  // n번째 피보나치 수를 계산
            int next = prev + curr;  // 다음 피보나치 수
            prev = curr;  // prev를 현재 값으로 갱신
            curr = next;  // curr를 다음 값으로 갱신
        }
        return curr;  // 최종적으로 n번째 피보나치 수 반환
    }
}

public class FibonacciSequence {
    public static void main(String[] args) {
        FibonacciSequences fibonacciSequences = new FibonacciSequences();
        int F = 8;  // 7번째 피보나치 수를 구하자
        
        // 반복문 방식으로 계산
        location = fibonacciSequences.Iterative(F);
        System.out.println("반복문 방식 결과: " + location);
    }
}

 

반복 방식 피보나치 수열의 특징

재귀 방식과 다르게 반복문을 사용하여 중복 계산을 빼고 계산하기 때문에 재귀 방식보다 매우 빠릅니다. 예를 들면 n이 120일 때 재귀 방식은 36년이 걸리지만 반복 방식은 120 나노초면 실행이 끝날 정도로 매우 빠릅니다.

 

반복 방식 피보나치 수열의 복잡도

시간 복잡도 : O(n)

공간 복잡도 : O(1) (추가 메모리 사용 없음)