Executando verificação de segurança...
1

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.

Carregando publicação patrocinada...