すばやく-数値のO(log N)算術演算の場合-N番目のフィボナッチ数を見つける私はそれについて考え、O(N)の間に機能するソリューションのみが頭に浮かぶことに気付きました。 しかし、解決策は後で見つかりました。
便宜上、表記から移動します




だから解決策
ナッツ[ 1、p。 112 ]は、次の形式の行列IDを提供します。
身元は証明なしで与えられますが、帰納法によって非常に簡単に証明されます。
右側のマトリックスは、Qマトリックスと呼ばれることもあります。
注:

アイデンティティからそれを得る



計算以来

マトリックスを用意しましょう






これは以下を参照します:

したがって、行列を計算するには




明らかに、木の高さは

計算時間を見積もる






また、nが2のべき乗でない場合はどうなりますか?
ここで疑問が生じます:もしも


どこで




一般に、行列積は可換ではありませんが、 乗算中のオペランドの順序は重要ですが、いわゆる 順列行列の可換性が尊重されます。 マトリックス



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

- 分解する
セットの形式での2の累乗の合計
。
- セットのすべての要素を計算する
。
- 計算する
。
このアルゴリズムの実行時間を推定します。
最初のステップは時間内に完了します



2番目のステップは


3番目のステップは


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



コード
コーディングに移りましょう。 次の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
.



MatrixFibonacci
IterationFibonacci
(, ). 10 000


n <tab> T1 <tab> T2
. .

, -


. gnuplot — .
P.S. , TeX- . , .