피보나치 수열을 재귀로 구현할 때 시간 복잡도가 O(2^n)인 이유와 개선 방법은?
보통 freeCodeCamp해설
fib(n) = fib(n-1) + fib(n-2)로 구현하면 fib(3)이 수십 번 중복 호출됩니다. 메모이제이션(하향식 DP)으로 계산 결과를 저장하거나, 반복문(상향식 DP)으로 아래부터 차례로 계산하면 O(n)으로 개선됩니다.
fib(n) = fib(n-1) + fib(n-2)로 구현하면 fib(3)이 수십 번 중복 호출됩니다. 메모이제이션(하향식 DP)으로 계산 결과를 저장하거나, 반복문(상향식 DP)으로 아래부터 차례로 계산하면 O(n)으로 개선됩니다.
