Usando formalidades matemáticas podemos usar também potênicas de matrizes especiais para obter um algoritmo que retorna o n-ésimo número de fibonnaci, com um melhor desempenho que um algoritmo recursivo aliás. São inumeras aplicações matemáticas na programação. Sou discente do curso de matemática computacional e reforço a importância da matemática na computação e na programação. Exemplifico abaixo o algoritmo usando potências de matrizes especiais para a obtenção do n-ésimo número de Fibonnaci.
import numpy as np
def fibmat(n):
"""
Algoritmo matricial para o cálculo dos números da sequência de Fibonacci.
Entrada:
n (int): número inteiro não negativo.
Saída:
(int): o valor de F_n
"""
# você deve iniciar a implementação desta função a partir daqui.
assert n >= 0
if n == 0:
return 0
elif n == 1:
return 1
else:
M = np.array([[1,1],[1,0]])
Mn = M
for i in range(n):
Mn = np.dot(M, Mn)
return Mn[1,1]
É apenas um algoritmo que foi retirado do meu repositório de trabalhos da cadeira de Cálculo Numérico.
Em relação a complexidade do algortimo, o algoritimo recursivo e não recursivo tem como complexidade exponêncial, ou seja,O(2^n). O algoritmo usando potências de matrizes especiais tem como complexidade linear, ou seja,O(n), uma diferença grande na comparação dos algoritmos.