보통 코딩을 배울 때, 피보나치 구현을 배울 때는 재귀(Recursion)를 이용한 방법으로 구현한다.
그러나 재귀 방식의 알고리즘은 시간복잡도가 O(n^2)로 아주 오래 걸리기 때문에 보통은 동적 프로그래밍(DP)를 이용하는 편이다. 동적 프로그래밍의 시간복잡도는 O(n)이다.
재귀 방식의 피보나치 수를 구하는 함수
def recursion(n):
if n==1 or n==2:
return 1
else:
return fibo(n-1) + fibo(n-2)
동적 프로그래밍 방식의 피보나치 수를 구하는 함수
def dp(n):
dp = [1,1]
if n==1 or n== 2:
return 1
for i in range(2,n):
dp.append(dp[i-1]+dp[i-2])
return dp[-1]
