✔️ محاسبه سریع فیبوناچی با روش ماتریسی!
برای محاسبه دنباله فیبوناچی معمولاً از روش بازگشتی استفاده میکنیم:
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
اما یک روش حرفهای با پیچیدگی O(log n) وجود دارد:
def fib(n):
def mat_pow(mat, power):
result = [[1,0],[0,1]]
while power > 0:
if power % 2 == 1:
result = mat_mult(result, mat)
mat = mat_mult(mat, mat)
power //= 2
return result
def mat_mult(a, b):
return [[a[0][0]*b[0][0] + a[0][1]*b[1][0],
a[0][0]*b[0][1] + a[0][1]*b[1][1]],
[a[1][0]*b[0][0] + a[1][1]*b[1][0],
a[1][0]*b[0][1] + a[1][1]*b[1][1]]]
if n == 0:
return 0
mat = [[1,1],[1,0]]
result = mat_pow(mat, n-1)
return result[0][0]
#پایتون | #الگوریتم | #بهینه_سازی | @learnpythonicy