[Python] 다이나믹 프로그래밍(6) - 피보나치 수열(동작분석)

• 이미 계산된 결과를 메모리에 저장하면 다음과 같이 색칠된 노드만 처리할 것을 기대할 수 있습니다.

• 실제로 호출되는 함수에 대해서만 확인해보면 다음과 같이 방문합니다.

피보나치 수열: 메모이제이션 동작 분석

• 메모이제이션을 이용하는 경우 피보나치 수열 함수의 시간 복잡도는 O(N)입니다.

d = [0] * 100

def fibo(x):
    print('f(' + str(x) + ')', end=' ')
    if x == 1 or x == 2:
        return 1
    if d[x] != 0:
        return d[x]
    d[x] = fibo(x - 1) + fibo(x - 2)
    return d[x]

fibo(6) 
# f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4)