08-피보나치 수열

1. 재귀 함수   // 시간 복잡도 : O(2^n)

def fivo(x):
  if x == 1 or x == 2 :
    return 1
    
  return fivo(x-1)+ fivo(x-2)

 

 

2. Top-down 방식 , Memoization 기법 사용 ( Cashing )   // 시간 복잡도 : O(N) 

# 계산된 피보나치 결과를 저장하는 리스트 선언 
result = [0] * 100 

def fivo(x):
  if x == 1 or x == 2 :
    return 1 
  
  if result[x] != 0 :
    return result[x]

  d[x]= fivo(x-1)+fivo(x-2)
  return d[x]

 

3. Bottom-up 방식 

# 계산된 피보나치 결과를 저장하는 리스트 선언 
result = [0] * 100 

result[1]=result[2]=1
n = 99 

for i in range(3,n+1):
  d[i] = d[i-1]+d[i-2]