En el trabajo del curso, se requirió escribir un algoritmo con complejidad logarítmica, que encontrará el número N de la secuencia de Fibonacci.
Algoritmo
Encontré varios artículos sobre este tema, todos ellos trataban de la clásica serie de números de Fibonacci. Para él, puedes aplicar esta fórmula:
Pero en mi trabajo se utilizaron series generalizadas, en las que los dos primeros números son cero y algún parámetro. Después de horas de búsqueda, encontré un comentario interesante en el que el autor da una fórmula para el hallazgo cíclico de cualquier secuencia lineal recurrente (incluida una serie de números de Fibonacci).
Aquí Q es una matriz de 2x2 cuyos elementos se pueden calcular fácilmente.
Sustituyendo algunos números de Fibonacci, encontramos que la matriz Q = [[0,1], [1,1]].
La fórmula final de la matriz, que contiene el número N-ésimo de la serie de Fibonacci generalizada, se puede escribir de la siguiente manera:
Fn es el número de Fibonacci deseado,
C es la clave,
n es el número ordinal del número
Obviamente, para la eficiencia de todo el algoritmo, es necesario usar el algoritmo más rápido para elevar la matriz Q a la potencia n. Este artículo me ayudó a lidiar con esto. Explica que para elevar una matriz a la potencia de n, puede dividir n en potencias de dos y luego elevar las matrices solo a estas potencias. Este enfoque da la complejidad O (log N).
Entonces solo queda multiplicar por la matriz [[C, C], [C, 0]] y obtener el elemento con el índice [0,1].
Implementación de 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]
Para comparar la eficiencia, el análogo más simple de este algoritmo se escribió usando un bucle:
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
Los puntos de referencia confirman nuestras expectativas: el algoritmo clásico lleva varias veces más tiempo ya en el número 10,000.
