피보나치 수열을 재귀로 구현할 때 시간 복잡도가 O(2^n)인 이유와 개선 방법은?

Q: 피보나치 수열을 재귀로 구현할 때 시간 복잡도가 O(2^n)인 이유와 개선 방법은?

같은 값을 중복 계산하기 때문이며, 메모이제이션이나 상향식 DP로 O(n)으로 개선할 수 있다 fib(n) = fib(n-1) + fib(n-2)로 구현하면 fib(3)이 수십 번 중복 호출됩니다. 메모이제이션(하향식 DP)으로 계산 결과를 저장하거나, 반복문(상향식 DP)으로 아래부터 차례로 계산하면 O(n)으로 개선됩니다.

보통 freeCodeCamp

보기 및 정답

A 같은 값을 중복 계산하기 때문이며, 메모이제이션이나 상향식 DP로 O(n)으로 개선할 수 있다

B 재귀 호출이 각 단계에서 1번만 일어나기 때문에 호출 트리가 선형적으로 증가한다

C 피보나치 수열은 재귀적 특성 때문에 어떠한 최적화 기법으로도 개선할 수 없는 문제이다

D 재귀를 반복문으로 변환하더라도 동일한 중복 계산이 그대로 발생하므로 시간 복잡도는 전혀 변하지 않는다

해설

fib(n) = fib(n-1) + fib(n-2)로 구현하면 fib(3)이 수십 번 중복 호출됩니다. 메모이제이션(하향식 DP)으로 계산 결과를 저장하거나, 반복문(상향식 DP)으로 아래부터 차례로 계산하면 O(n)으로 개선됩니다.

코딩, 제대로 배우고 싶다면?

개념 확인은 퀴즈로, 실력은 실전 프로젝트로.
투더제이 코딩클래스에서 시작하세요.

정규반 살펴보기

피보나치 수열을 재귀로 구현할 때 시간 복잡도가 O(2^n)인 이유와 개선 방법은?

해설

코딩, 제대로 배우고 싶다면?

관련 문제

시장과 사람의 답을 봤다면,다음 결과물의 구조를 고릅니다.

시장과 사람의 답을 봤다면,
다음 결과물의 구조를 고릅니다.