Algorithme en temps exponentiel

#entrée : un entier n
#sortie : le n^e terme de la suite de Fibonacci
#algorithme en temps exponentiel à cause des appels récursifs qui se chevauchent
def fib(n):
    if n <= 1:
        return n
    else:
        return fib(n-1) + fib(n-2)

fib(6)

8

Algorithme en temps quadratique

#entrée : un entier n
#sortie : le n^e terme de la suite de Fibonacci
#algorithme en temps quadratique (boucle en O(n) et addition en O(n))    
def fib2(n):
    T = (n+1)*[0]
    T[1] = 1
    for i in range(2,n+1):
        T[i] = T[i-1] + T[i-2]
    return T[n]

fib2(6)

8

Algorithme de la même complexité que la multiplication

 #entrée : un entier n
#sortie : le n^e terme de la suite de Fibonacci
#algorithme en temps O(M(n)) où M(n) est la complexité d'une multiplication de nombres de n bits
def fib3(n):
    
    #entrée : deux matrices A et B de taille 2X2 avec des nombres sur k bits
    #sortie : la matrice A*B
    #calcul direct. Nb constant d'opérations arithmétiques.
    #en O(M(k)) si M(k) est la complexité pour faire une multiplication de deux nombres de k bits chacun
    def matrix22mult(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]]]
    
    #entrée: une matrice A de taille 2X2, n entier
    #sortie : la matrice A^n
    #calcul avec exponentiation rapide O(log n M(n)) mais en fait en O(M(n))
    def matrix22expo(A, n):
        if n == 0:
            return [[1, 0], [0, 1]]
        else:
            B = matrix22expo(A, n//2)
            if n % 2 == 0:
                return matrix22mult(B, B)
            else:
                return matrix22mult(A, matrix22mult(B, B))
            
    return matrix22expo([[0, 1], [1, 1]], n) [0][1]

fib(6)

8

Algorithme qui manipule des nombres irrationnels (avec tous les pbs d'arrondis qui vont avec)

import math

#entrée : un entier n
#sortie : le n^e terme de la suite de Fibonacci
#algorithme avec la formule de Binet
def fib4(n):
    phi = (1 + math.sqrt(5)) / 2
    phi2 = - 1 / phi
    return (phi ** n - phi2 ** n) / math.sqrt(5)

fib4(6)

8.000000000000002