파 이 썬 을 어떻게 사용 하여 피 보 나치 수열 을 실현 합 니까?

피 보 나치 수열(Fibonacci)은 최초 로 인도 수학자 Gopala 가 제기 했다.첫 번 째 로 피 보 나치 수열 을 진정 으로 연구 한 것 은 이탈리아 수학자 Leonardo Fibonacci 이다.피 보 나치 수열 의 정 의 는 매우 간단 하 다.수학 함수 로 표시 할 수 있다.

수열 은 0 과 1 에서 시작 되 고 그 다음 의 수 는 앞의 두 수 를 더 한 것 이다.예 를 들 어 피 보 나치 수열 의 10 개 수 는 0,1,1,2,3,5,8,13,21,34 이다.
Python 으로 피 보 나치 수열 을 실현 하 는 흔 한 표기 법 은 세 가지 가 있 습 니 다.각 알고리즘 의 집행 효율 도 큰 차이 가 있 습 니 다.면접 에서 도 가끔 질문 을 받 을 수 있 습 니 다.보통 면접 을 볼 때 재 귀적 으로 쓰 면 끝 나 는 것 이 아니 라 시간 복잡 도가 어떤 지,공간 복잡 도가 어떤 지,개선 할 점 이 있 는 지 물 어 봅 니 다.
귀속 법
재 귀 란 함수 의 정의 에서 함수 자체 의 방법 을 사용 한 것 을 말한다.

def fib_recur(n):
assert n >= 0
if n in (0, 1):
return n
return fib_recur(n - 1) + fib_recur(n - 2)
for i in range(20):
print(fib_recur(i), end=" ")
>>> 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 

재 귀 는 코드 가 가장 간결 한 방법 이지 만 효율 이 매우 낮다.대량의 중복 계산 이 발생 하기 때문에 시간 복잡 도 는 O(1.618^n)이 고 1.618 은 금 분할 이다.동시에 Python 에서 재 귀 하 는 최대 깊이 는 1000 이 므 로 재 귀 로 해결 하 는 것 은 바람 직 한 방법 이 아니다.
추이 법
푸 시 법 은 0 과 1 에서 시작 하여 앞의 두 항목 을 더 해 각각 3,4 번 째 수 를 구하 고 n 번 째 수의 값 을 구 하 는 것 이다.

def fib_loop(n):
a, b = 0, 1
for i in range(n):
a, b = b, a + b
return a
for i in range(20):
print(fib_loop(i), end=" ")
>>> 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 

이런 알고리즘 은 시간 이 복잡 한 것 은 O(n)로 선형 성장 을 보이 고 데이터 의 양 이 많 으 면 속도 가 뒤로 갈수 록 느 려 집 니 다.
위의 두 가지 방식 은 모두 나 누 어 다스 리 는 사상 을 사용 하 는 것 이다.바로 큰 문 제 를 작 게 만 든 다음 에 작은 문제 의 구 해 를 이용 하여 목표 문제 의 답 을 얻 는 것 이다.
행렬 법
는 대학 컴퓨터 학과 저 학년 의 과정 이다.이 과목 은 바로 행렬 을 가 르 쳤 다.그 때 는 이 물건 을 배 우 는 것 이 지루 하고 쓸모 가 없다 고 생각 했다.일 을 한 후에 야 기계 학습,데이터 분석,데이터 모델 링 을 할 때 큰 도움 이 되 고 책 을 사용 할 때 미움 이 적 다 는 것 을 알 게 되 었 다.사실 행렬 의 본질은 선형 방정식 이다.
피 보 나치 수열 에서 두 개의 인접 한 항목 은 각각 F(n)와 F(n-1)이다.만약 에 이 두 수 를 2 행 1 열의 행렬 로 간주한다 면 다음 과 같이 표시 할 수 있다.

F(n)=F(n-1)+F(n-2)가 있 기 때문에:

반추 를 통 해 사실 그것 은 두 행렬 의 곱 으로 얻 은 것 이다.

이에 따라 유추 하 다.

마지막 으로 출시 가능:

따라서 F(n)의 값 을 요구 하려 면 오른쪽 행렬 의 n-1 차방 의 값 을 구 할 수 있 고 마지막 으로 두 행렬 의 곱 을 구 할 수 있 으 며 새로운 행렬 의 첫 줄 의 첫 번 째 열 값 을 취하 면 된다.예 를 들 어 n=3 시,

F(3)의 값 2,F(2)의 값 이 1 이라는 것 을 알 수 있다.멱 연산 은 이분 가속 을 사용 할 수 있 기 때문에 행렬 법의 시간 복잡 도 는 O(log n)이다.
우 리 는 과학적 인 계산 패키지 numpy 로 행렬 법 을 실현 할 수 있다.

import numpy
def fib_matr(n):
return (numpy.matrix([[1, 1], [1, 0]]) ** (n - 1) * numpy.matrix([[1], [0]]))[0, 0]
for i in range(20):
print(int(fib_matr(i)), end=" ")
>>> 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 

3 중 서로 다른 알고리즘 효율 대비:

위의 그림 을 통 해 알 수 있 듯 이 재 귀 법의 효율 이 놀 라 울 정도 로 낮 고 행렬 법 은 데이터 의 양 이 비교적 많 을 때 그의 장점 을 나타 낸다.전달 법 은 데이터 가 커지 면서 걸 리 는 시간 도 점점 커진다.
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.