피 보 나치 수
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),금 분할 율 을 저장 하 는 데 사용 되 는 공간.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
