피 보 나치 수

방법 1:귀속

public static int fib(int n) {
   if (n <= 1) {
      return 1;
   }
   return fib(n - 1) + fib(n - 2);
}

복잡 도 분석
시간 복잡 도:O(2^N)O(2 N )。이것 은 피 보 나 계 수 를 계산 하 는 가장 느 린 방법 이다.지수 시간 이 필요 하기 때문이다.공간 복잡 도:O(N)O(N),스 택 에서 우 리 는 N 과 정비례 하 는 공간 크기 가 필요 합 니 다.이 스 택 은 fib(N)의 함수 호출 을 추적 합 니 다.스 택 이 계속 증가 함 에 따라 충분 한 메모리 가 없 으 면 StackOverflow Error 를 초래 할 수 있 습 니 다.
방법 2:공식 법
황금 분할 율 로 계산  N  피 보 나치 수

public int fib(int N) {
        double goldenRatio = (1 + Math.sqrt(5)) / 2;
        return (int)Math.round(Math.pow(goldenRatio, N)/ Math.sqrt(5));
    }

복잡 도 분석
시간 복잡 도:O(1).상수 의 시간 복잡 도 는 우리 가 Binet 공식 을 바탕 으로 계산 하기 때문에 순환 이나 재 귀 를 사용 하지 않 았 다.공간 복잡 도:O(1),금 분할 율 을 저장 하 는 데 사용 되 는 공간.