Pythonはフィボナッチの第n項を解決する解法を実現します。マトリックス乗算＋高速べき乗を含みます。

フィボナッチ数列
まずフィボナッチの数列を定義します。

すなわち、数列の0番目の項目です。

アルゴリズム1：再帰
再帰的に計算されるノードの個数はO（2̿）のレベルであり、効率が低く、大量の繰返し計算が存在する。
たとえば:
f(10)=f(9)+f(8)
f(9)=f(8)+f(7)は8を繰り返す。
f(8)=f(7)+f(6)は7を繰り返す。
時間の複雑さはO（2̿）で、とても遅いです。

def F1(n):
    if n <= 1: return max(n, 0)  #    
    return F1(n-1)+F1(n-2)  #   

アルゴリズム二：記憶化検索
大きな行列を作って中間結果を記録します。状態が計算されたら、直接に表を調べます。そうでなければ、再帰的に計算します。
全部でn個の状態があり、各状態の複雑さを計算するのはO（1）であるため、時間複雑度はO（n）である。しかし、再帰的な計算なので、再帰的な層数が多すぎると、ボンドが破裂します。

res = [None]*100000
def F2(n):
    if n <= 1: return max(n, 0)
    if res[n]: return res[n]  #               
    res[n] = F2(n-1)+F2(n-2)  #       
    return res[n]

アルゴリズム3：デリバリー
大きな行列を作って、各数の値を記録します。循環的に計算する。
n状態を合計して計算するので，時間複雑度はO（n）である。しかし、長いn配列を開く必要があります。メモリはボトルネックになります。

def F3(n):
    if n <= 1: return max(n, 0)
    res = [0, 1]
    for i in range(2,n+1):
        res.append(res[i-1]+res[i-2])
    return res[n]

アルゴリズム4：再帰＋スクロール変数
優れた解法です。注意深く観察すると、私たちは前の二つの項目の値を記録するだけでいいです。すべての値を記録する必要がないので、スクロール変数で転送できます。
時間複雑さはまだO（n）であるが、空間複雑さはO（1）になる。

def F4(n):
    if n <= 1: return max(n, 0)
    fn, f0, f1 = 0, 1, 0  # fn     ，f0  0 ，f1    ，
    for i in range(2, n+1):
        fn = f0 + f1  #     
        f0, f1 = f1, fn  #     
    return fn

アルゴリズム5：マトリックス乗算+高速べき乗
行列演算の性質を利用して，通項式をべき乗次形式に変え，次いで第n項を平方増倍（高速べき乗）法で解いた。
まず通式を言います

数学帰納法を利用して証明する：
ここのa 0、a 1、a 2はフィボナッチの第数項に対応します。

証明済み
ですから、私たちが欲しいのはAnを手に入れるために、Aを必要として、第一行の第二要素を取ればいいです。
単純に0からn乗を循環させるだけなら、時間の複雑さは依然としてO（n）であり、前のものより速くない。乗方の次のような性質、すなわち早いべき乗を考慮することができます。

このようにlogn演算だけで結果が得られます。時間複雑度はO（logn）です。

def mul(a, b):  #             
    c = [[0, 0], [0, 0]]  #           ，    
    for i in range(2):  # row
        for j in range(2):  # col
            for k in range(2):  #          
                c[i][j] += a[i][k] * b[k][j]
    return c
def F5(n):
    if n <= 1: return max(n, 0)
    res = [[1, 0], [0, 1]]  #     ，   1
    A = [[1, 1], [1, 0]]  # A  
    while n:
        if n & 1: res = mul(res, A)  #   n   ，    n=1    
        A = mul(A, A)  #    
        n >>= 1  #   2，    
    return res[0][1]

全体的には難しくないです。考え方を広げるのに適しています。Pythonに関する資料は他の関連記事に注目してください。これからも応援してください。