피보나치 수열의 효율적인 해법과 시간 복잡도 분석 시리즈 3

피보나치 수열과 시간 복잡도 분석 시리즈 중 두 번째의 마지막 효과적인 해법을 갱신하다.

6.? 무미 재귀의 실용적인 방안.

앞서 언급했듯이 피보나치 수열의 일반적인 재귀적 해법의 시간 복잡성은 O (1.6 18 N) 로 기하급수적으로 증가하여 실용적 가치가 없다.

재귀 호출 프로세스를 자세히 살펴보면 calculate _ Fibonacci _ sequence (n-1)+calculate _ Fibonacci _ sequence (

그런 다음 반복 중에 중간 결과를 사전에 저장하고, 사전에서 각 반복 호출을 검사하여 매개변수가 같은 호출인지 확인하고, 그럴 경우 사전에 저장된 값을 직접 반환합니다.

이렇게 하면 알고리즘의 시간 복잡성이 O(n) 로 줄어듭니다. 캐싱 기술을 통해 시간 복잡성이 사용 가능한 수준으로 낮아졌다.

이 재귀 캐시 데코레이터를 쓰기 시작합니다. Decorators 는 Python 에서 널리 사용되고 있으며, 많은 경우 모듈식 캐스케이딩이 용이합니다.

효과를 시험해 봅시다. 100 입니다.

원래 막혔던 상황이 없어졌는데, 결국 초 만에 나왔다.

네, 1200 항목을 다시 계산해 보세요.

스택 오버플로 오류

실용성의 장애이기도 합니다. 파이썬의 기본 스택 공간은 크지 않고 1000 만 있습니다. 파이썬 당국은 재귀를 추천하지 않고 가능한 반복 루프로 쓴다. 공식적인 생각은 기본적으로 작은 스택 공간을 설정하는 것이다. 프로그램에 너무 깊은 재귀가 있으면 런타임 초기에 노출하고 다시 쓸 수 있습니다.

그러나 재귀적인 표기법은 확실히 간결하고 명료하며 효율성에 대한 요구가 없을 때 사용할 수 있다.

재귀 과정에서 오버플로우 오류를 해결하는 한 가지 방법은 설정의 한계를 동적으로 늘리는 것입니다.

Decorator 를 사용하는 것이 그것을 실현하는 우아한 방법이라고 생각할 수 있습니다.

그러나 반복 함수 실행을 고려한 후 recursionlimit 의 초기 값을 복원하려는 경우.

Decorator 는 혼자서 이 목표를 달성할 수 없다. (좋은 생각이 있다면 아래에 댓글을 달아 토론해 주세요.)

함수 매개 변수를 전달하여 이 솔루션을 구현합니다.

효과를 시험해 봅시다.

실행 시간은 이전 예와 동일하며 총 시간은 0.0 12642 초입니다.

문제가 해결되다

실용적인 가치가 없는 피보나치 수열의 재귀적 해석을 사용 가능한 재귀적 해법으로 만들다.

미완이 계속되다.

피보나치 수열의 효율적인 해법과 시간 복잡도 분석 4