In der Kursarbeit musste ein Algorithmus mit logarithmischer Komplexität geschrieben werden, der die N-te Zahl aus der Fibonacci-Sequenz ermittelt.
Algorithmus
Es wurden mehrere Artikel zu diesem Thema gefunden, die sich alle mit der klassischen Reihe von Fibonacci-Zahlen befassten. Für ihn können Sie diese Formel anwenden:
In meiner Arbeit wurden jedoch verallgemeinerte Reihen verwendet, in denen die ersten beiden Zahlen Null und einige Parameter sind. Nach stundenlangem Suchen stieß ich auf einen interessanten Kommentar, in dem der Autor eine Formel für das zyklische Auffinden linearer wiederkehrender Sequenzen (einschließlich einer Reihe von Fibonacci-Zahlen) angibt.
Hier ist Q eine 2x2-Matrix, deren Elemente leicht berechnet werden können.
Wenn wir einige Fibonacci-Zahlen einsetzen, stellen wir fest, dass die Matrix Q = [[0,1], [1,1]] ist.
Die endgültige Formel der Matrix, die die N-te Zahl der verallgemeinerten Fibonacci-Reihe enthält, kann wie folgt geschrieben werden:
Fn ist die gewünschte Fibonacci-Zahl,
C ist der Schlüssel,
n ist die Ordnungszahl der Zahl
Für die Effizienz des gesamten Algorithmus ist es natürlich erforderlich, den schnellsten Algorithmus zu verwenden, um die Matrix Q auf die Potenz n zu bringen. Dieser Artikel hat mir geholfen, damit umzugehen. Es wird erklärt, dass Sie, um eine Matrix auf die Potenz von n zu erhöhen, n in Zweierpotenzen aufteilen und dann die Matrizen nur auf diese Potenzen erhöhen können. Dieser Ansatz ergibt die Komplexität O (log N).
Dann bleibt nur noch mit der Matrix [[C, C], [C, 0]] zu multiplizieren und das Element mit dem Index [0,1] zu erhalten.
Python-Implementierung
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]
Um die Effizienz zu vergleichen, wurde das einfachste Analogon dieses Algorithmus unter Verwendung einer Schleife geschrieben:
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
Benchmarks bestätigen unsere Erwartungen: Der klassische Algorithmus benötigt bereits bei der 10.000sten Zahl ein Vielfaches mehr Zeit.
