コース作業では、フィボナッチ数列からN番目の数を見つける対数の複雑さを持つアルゴリズムを作成する必要がありました。
アルゴリズム
このトピックに関するいくつかの記事が見つかりました。それらはすべて、フィボナッチ数の古典的なシリーズを扱っていました。彼の場合、次の式を適用できます。
しかし、私の仕事では、最初の2つの数値がゼロで、いくつかのパラメーターがある一般化されたシリーズが使用されました。何時間も検索した後、著者が線形反復シーケンス（一連のフィボナッチ数を含む）を周期的に見つけるための公式を示す興味深い解説に出くわしました。
ここで、Qは要素を簡単に計算できる2x2行列です。
いくつかのフィボナッチ数を代入すると、行列Q = [[0,1]、[1,1]]であることがわかります。
一般化されたフィボナッチ数列のN番目の数を含む行列の最終式は、次のように記述できます。
Fnは目的のフィボナッチ数、
Cはキー、
nは数の序数です。
明らかに、アルゴリズム全体の効率を上げるには、最速のアルゴリズムを使用して行列Qをn乗する必要があります。この記事は、これに対処するのに役立ちました。行列をnの累乗に上げるには、nを2の累乗に分割してから、行列をこれらの累乗にのみ上げることができると説明されています。このアプローチは複雑さO（log N）を与えます。
次に、行列[[C、C]、[C、0]]を乗算し、インデックス[0,1]の要素を取得するだけです。
Pythonの実装
class FiboMatrix:
key = 0
matrix_cur = [[0,0], [0,0]]
matrix_one = [[0,1], [1,1]]
def __init__(self, key):
self.key = key
self.matrix_cur = [[key, key], [key, 0]]
self.PowsBuffer = {}
#
def MultiplyMatrix(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]
return [[a11, a12], [a21, a22]]
def PowMatrix(self, M: list, p: int):
""" .
2x2 .
"""
if p == 1:
return M
if p in self.PowsBuffer:
return self.PowsBuffer[p]
K = self.PowMatrix(M, int(p / 2))
R = self.MultiplyMatrix(K, K)
self.PowsBuffer[p] = R
return R
def GetNum(self, n):
if n == 0:
return 0
if n == 1:
return 1
# n
powers = []
p = 0
for digit in reversed(bin(n)[2:]):
if digit == '1':
powers.append(int(pow(2, p)))
p += 1
matrices = [self.PowMatrix(FiboMatrix.matrix_one, p)
for p in powers]
#
while len(matrices) > 1:
M1 = matrices.pop()
M2 = matrices.pop()
R = self.MultiplyMatrix(M1, M2)
#
matrices.append(R)
self.matrix_cur = self.MultiplyMatrix(self.matrix_cur, matrices[0])
# F1 F2 ,
return self.matrix_cur[0][1]
効率を比較するために、このアルゴリズムの最も単純な類似物は、ループを使用して記述されました。
def Fib(num, key):
fib_1 = 0
fib_2 = key
for dec in range(num):
fib_1, fib_2 = fib_2, fib_1+fib_2
return fib_2
ベンチマークは私たちの期待を裏付けています。古典的なアルゴリズムは、すでに10,000番目の数値で数倍の時間がかかります。
