따라할 jupyter 노트북을 엽니다. 다음 코드 블록은 ipynb 노트북의 셀입니다.

전제 조건:

재귀를 사용하여 피보나치 수열의 n번째 항을 찾는 방법을 알아야 합니다.

피보나치

video에 링크합니다.

from timeit import timeit

이제 먼저 표준 재귀 함수를 만들어 보겠습니다.

def fibo(n: int) -> int:
    # without memoization
    if n <= 2:
        return 1
    return fibo(n-1) + fibo(n-2)

이제 시간 복잡도를 n로 줄이는 메모이제이션을 사용해 봅시다.

def memo_fibo(n: int, memo: dict = {}) -> int:
    # with memoization
    if n in memo:
        return memo[n]
    if n <= 2:
        return 1
    memo[n] = memo_fibo(n-1, memo) + memo_fibo(n-2, memo)
    return memo[n]

값을 n로 설정합시다(우리가 찾고자 하는 피보나치 수열의 항)

n = 40

정상적인 방법으로 실행합시다. (여기서는 실행 시간을 찾기 위해 magic command of Jupyter Notebook 을 사용했습니다.)

%%timeit -n 1 -r 10
fibo(n)

33.4 s ± 257 ms per loop (mean ± std. dev. of 10 runs, 1 loop each)

이제 메모를 사용한 함수를 실행해 봅시다.

%%timeit -n 1 -r 10
memo_fibo(n)

The slowest run took 86.52 times longer than the fastest. This could mean that an intermediate result is being cached.
3.6 µs ± 9.59 µs per loop (mean ± std. dev. of 10 runs, 1 loop each)

그 차이는 극명합니다. 33.4 s에서 3.6 µs로 .

따라서 메모이제이션을 사용하면 실행 시간이 크게 달라집니다.

'피보나치'라는 이름은 나중에 피보나치로 알려지게 된 13세기 이탈리아 수학자 피사의 레오나르도(Leonardo of Pisa)에서 유래했습니다.

그러나 우리가 일반적으로 '피보나치 수'라고 부르는 것은 기원전 2세기 인도 사상가 Acharya Pingala의 작업에서 가장 먼저 언급되었습니다.