📈 👩‍❤️‍👩 🍥 OごとのN番目のフィボナッチ数（log N） 🐈 🙎🏼 🚴🏼

ABBYYでの就職についての記事を読んでいるときに、その問題について言及しました。

すばやく-数値のO（log N）算術演算の場合-N番目のフィボナッチ数を見つける

私はそれについて考え、O（N）の間に機能するソリューションのみが頭に浮かぶことに気付きました。しかし、解決策は後で見つかりました。

便宜上、表記から移動します

に

。セットにも表記法を使用します。 $\ mathbb {N} _0 = \左\ {0、1、2、3、... \右\}$ 非負の整数 $\ mathbb {N} _1 = \左\ {1、2、3、... \右\}$ 正の整数です。事実、さまざまな数学的伝統では、多くの自然数に0が含まれる場合と含まれない場合があります。したがって、国際数学のテキストでは、これを明示的に示すことが推奨されています。

だから解決策

ナッツ[ 1、p。 112 ]は、次の形式の行列IDを提供します。
$\ begin {pmatrix} F_ {n + 1}＆F_n \\ F_n＆F_ {n-1} \ end {pmatrix} = \ begin {pmatrix} 1＆1 \\ 1＆0 \ end {pmatrix} ^ n$
身元は証明なしで与えられますが、帰納法によって非常に簡単に証明されます。
右側のマトリックスは、Qマトリックスと呼ばれることもあります。
注：
$Q = \ begin {pmatrix} 1＆1 \\ 1＆0 \ end {pmatrix}$
アイデンティティからそれを得る $F_n = Q ^ {n-1} \左（1,1 \右）$ 。つまり計算する F_n

行列を計算する必要があります $Q ^ {n-1}$ そして、最初の行の最初の要素（1から番号付け）を取得します。

計算以来 F_n

行列を累乗することに還元された場合、このプロセスをより詳細に検討します。
マトリックスを用意しましょう

力に引き上げられる $n \ in \ mathbb {N} _1$ 。また、

2のべき乗、つまり $n = 2 ^ i、i \ in \ mathbb {N} _0$ 。
M ^ n

ツリーとして表すことができます：

これは以下を参照します：
$M ^ n = M ^ {n / 2} \ cdot M ^ {n / 2} = ... = \ prod ^ {n} _ {1} M ^ 1$ 。
したがって、行列を計算するには M ^ n

行列を計算する必要があります $M ^ {n / 2}$ そしてそれ自体で乗算します。計算する $M ^ {n / 2}$ あなたは同じことをする必要があります $M ^ {n / 4}$ など
明らかに、木の高さは $\ log n$ 。
計算時間を見積もる M ^ n

。マトリックス

ある程度までは一定のサイズを持ちます。したがって、2つの行列の任意の程度への乗算は、 $O \左（1 \右）$ 。そのような乗算はすべて実行する必要があります $\ log_2n$ 。したがって、計算の複雑さ M ^ n

等しい $O \左（\ log n \右）$ 。

また、nが2のべき乗でない場合はどうなりますか？

ここで疑問が生じます：もしも

2のべき乗ではありませんか？任意の自然数

は、2のべき乗である数の合計として分解できます。繰り返しは行われません（2進数から10進数に変換するたびにこれを行います）。つまり
$n = \ sum_ {p \ in P} 2 ^ p$ 、
どこで $P_n \サブセット\ mathbb {N} _0$ -コンクリートが何度も通過する

。思い出すと

行列の次数である場合、次のようになります。
$M ^ n = \ prod_ {p \ in P_n} M ^ {2 ^ p}$ 。
一般に、行列積は可換ではありませんが、乗算中のオペランドの順序は重要ですが、いわゆる順列行列の可換性が尊重されます。マトリックス M ^ i

はの順列です

、 $i、j \ in \ mathbb {N} _0$ 。したがって、乗算するときにオペランドの順序を覚えておく必要はありません。

したがって、計算アルゴリズム M ^ n

以下のステップとして表すことができます。

分解するセットの形式での2の累乗の合計。
セットのすべての要素を計算する $S = \左\ {M ^ p | p \ in P_n \右\}$ 。
計算する $M ^ n = \ prod_ {s \ in S} s$ 。

このアルゴリズムの実行時間を推定します。
最初のステップは時間内に完了します $O \左（\左\ lfloor \ log_2n \ rfloor + 1 \右）= O \左（\ log n \右）$ どこで $\ lfloor log_2 n \ rfloor + 1$ -ビット数

。
2番目のステップは $O \ left（\ left \ left（\ lfloor \ log_2 n \ rfloor + 1 \ right）\ cdot \ log_2 n \ right）= O \ left（\ left \ log ^ 2 n \ right）$ なぜならもう完了する必要はありません $\ lfloor log_2 n \ rfloor + 1$ 行列を累乗します。
3番目のステップは $O \左（\左\ \ lfloor \ log_2 n \ rfloor \右）= O \左（\左\ログn \右）$ なぜならもう行列の乗算を実行する必要はありません $\ lfloor log_2 n \ rfloor$ 回。

最適化

このアルゴリズムの実行時間を改善することは可能ですか？はい、できます。 2番目のステップでは、セット内の行列を計算する方法

。私たちはそれらについてそれぞれ知っている

2のべき乗です。ツリーのある図に戻ると、これらはすべてツリーの特定の階層にあり、大きな階層を計算するには、小さな階層を計算する必要があります。メモ化手法を適用し、計算された行列をツリーのすべての層に保存すると、2番目のステップの作業時間を短縮できます。 $O \左（\ log n \右）$ アルゴリズム全体の実行時間もアップしています $O \左（\ log n \右）$ 。これは、問題の状態によって必要なものです。

コード

コーディングに移りましょう。次の2つの理由から、Pythonでアルゴリズムを実装しました。

擬似コードを置き換えるのに十分な表現力があります。
透過的な長演算があります。

これは次のとおりです。

class MatrixFibonacci:
    Q = [[1, 1],
         [1, 0]]

    def __init__(self):
        self.__memo = {}

    def __multiply_matrices(self, M1, M2):
        """ 
        (       2x2)."""

        a11 = M1[0][0]*M2[0][0] + M1[0][1]*M2[1][0]
        a12 = M1[0][0]*M2[0][1] + M1[0][1]*M2[1][1]
        a21 = M1[1][0]*M2[0][0] + M1[1][1]*M2[1][0]
        a22 = M1[1][0]*M2[0][1] + M1[1][1]*M2[1][1]
        r = [[a11, a12], [a21, a22]]
        return r

    def __get_matrix_power(self, M, p):
        """    ( p   )."""

        if p == 1:
            return M
        if p in self.__memo:
            return self.__memo[p]
        K = self.__get_matrix_power(M, int(p/2))
        R = self.__multiply_matrices(K, K)
        self.__memo[p] = R
        return R

    def get_number(self, n):
        """ n-  
        (  n    )."""
        if n == 0:
            return 0
        if n == 1:
            return 1
        #     ,   ,
        # .. 62 = 2^5 + 2^4 + 2^3 + 2^2 + 2^0 = 32 + 16 + 8 + 4 + 1.
        powers = [int(pow(2, b))
                  for (b, d) in enumerate(reversed(bin(n-1)[2:])) if d == '1']
        #  ,   pythonic: http://pastebin.com/h8cKDkHX

        matrices = [self.__get_matrix_power(MatrixFibonacci.Q, p)
                    for p in powers]
        while len(matrices) > 1:
            M1 = matrices.pop()
            M2 = matrices.pop()
            R = self.__multiply_matrices(M1, M2)
            matrices.append(R)
        return matrices[0][0][0]

mfib = MatrixFibonacci()
for n in range(0, 128):
    num = mfib.get_number(n)
    print(num)

. :

def get_number(self, n):
    if n == 0:
        return 0
    a = 0
    b = 1
    c = 1
    for i in range(n-1):
        c = a + b
        a = b
        b = c
    return c