검지 Offer Java 섹션 문제 10: 피보나치 수열

1320 단어
제목 1: 모두가 피보나치 수열을 알고 있습니다. 지금 정수 n을 입력해 주십시오. 피보나치 수열의 n항을 출력해 주십시오. (0부터, 0항은 0).n<=39

연습 주소


https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3

메서드 1: 반복

public class Solution {
    public int Fibonacci(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

복잡도 분석

  • 시간 복잡도: O(nlogn)..
  • 공간 복잡도: O(nlogn)..

  • 메서드 2: 순환

    public class Solution {
        public int Fibonacci(int n) {
            if (n <= 0) {
                return 0;
            }
            if (n == 1) {
                return 1;
            }
            int last = 0, result = 1;
            for (int i = 2; i <= n; i++) {
                result += last;
                last = result - last;
            }
            return result;
        }
    }
    

    복잡도 분석

  • 시간 복잡도: O(n)..
  • 공간 복잡도: O(1)..

  • 제목 2: 개구리 한 마리가 한 번에 1계단을 올라갈 수도 있고 2계단을 올라갈 수도 있다.이 개구리가 n급의 계단을 뛰어오르는 데는 모두 몇 가지 점프법이 있는지 구해라.

    연습 주소


    https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4

    답안을 참고하다


    실제는 바로 피보나치 수열로 이전 문제 해법과 유사하다.
    검지 Offer Java 버전 디렉토리 검지 Offer Java 버전 테마

    좋은 웹페이지 즐겨찾기