Dalam pekerjaan kursus, diharuskan menulis algoritma dengan kompleksitas logaritmik, yang akan menemukan angka ke-N dari deret Fibonacci.
Algoritma
Menemukan beberapa artikel tentang topik ini, semuanya berhubungan dengan deret klasik bilangan Fibonacci. Baginya, Anda bisa menerapkan rumus ini:
Tetapi dalam pekerjaan saya, seri umum digunakan, di mana dua angka pertama adalah nol dan beberapa parameter. Setelah berjam-jam mencari, saya menemukan komentar menarik di mana penulis memberikan rumus untuk temuan siklik dari setiap urutan berulang linier (termasuk serangkaian angka Fibonacci).
Di sini Q adalah matriks 2x2 yang elemen-elemennya dapat dihitung dengan mudah.
Mengganti beberapa bilangan Fibonacci, kita menemukan bahwa matriks Q = [[0,1], [1,1]].
Rumus akhir dari matriks, yang berisi angka ke-N dari deret Fibonacci umum, dapat ditulis sebagai berikut:
Fn adalah bilangan Fibonacci yang diinginkan,
C adalah kuncinya,
n adalah nomor urut dari nomor tersebut
Jelasnya, untuk efisiensi seluruh algoritme, perlu menggunakan algoritme tercepat untuk menaikkan matriks Q ke pangkat n. Artikel ini membantu saya mengatasinya . Ini menjelaskan bahwa untuk menaikkan matriks ke pangkat n, Anda dapat membagi n menjadi pangkat dua dan kemudian menaikkan matriks hanya ke pangkat ini. Pendekatan ini memberikan kompleksitas O (log N).
Kemudian tinggal mengalikan dengan matriks [[C, C], [C, 0]] dan mendapatkan elemen dengan indeks [0,1].
Implementasi 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]
Untuk membandingkan efisiensi, analog paling sederhana dari algoritma ini ditulis menggunakan loop:
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
Tolok ukur mengkonfirmasi harapan kami: algoritme klasik membutuhkan waktu beberapa kali lebih banyak pada angka ke-10.000.
