콘텐츠로 건너뛰기
Home » Fast Fibonacci Transform

Fast Fibonacci Transform

Fast Fibonacci Transform

빠른 피보나치 항 구하기 피보나치 수열은 0, 1, 1, 2, 3, 5, 8,… 과 같이 앞의 두 항의 합이 그 앞의 항이 되는 수열이다. 피보나츼 수열의 n 항을 구하는 함수는 보통 이렇게 많이 작성한다. def fib(n): if n < 3: return (0, 1)[n] return fib(n-1) + fib(n-2) 하지만 이 함수는 지극히 비효율적이라 %time fib(35) Wall time: 7.05 s Out[7]: 9227465 이런 처참한 성능이 나온다. 이는 한 번 계산했던 값을 계속 재계산하기 때문인데, 이런 문제를 피하기위해서는 메모이제인션이라는 캐싱 기법을 쓴다. #… 더 보기 »Fast Fibonacci Transform