Complexité Fibonacci

La suite de Fibonacci est un exemple intéressant pour comparer la complexité en temps de calcul et occupation mémoire de plusieurs solutions algorithmiques.

La suite de Fibonacci est une suite de nombres (entiers) où chaque terme est la somme des deux termes précédents, les deux premiers étant 0 et 1 : 0, 1, 1, 2, 3, 5, 8, …

L’objectif est de comparer les complexités de différentes versions des fonctions calculant la n-ième terme de la suite de Fibonacci :

• récursive — intuitive
• récursive avec mémoïsation (compromis temps-mémoire)
• itérative

Ces fonctions ont été conçues a des fins pédagogiques. fiborec et fibomemo sont récursives. Quelques précisions :

• fiborec a été adoptée à des fins pédagogiques, le code simplifié serait :

def fiborec(n: int) -> int:
    return n if n <= 1 else fiborec(n - 1) + fiborec(n - 2)
        #ce qui correspond au code suivant:
        #if n <= 1:
            #v = n
        #else:
            #v = fiborec(n - 1) + fiborec(n - 2)
        #return v

• fibomemo nécessite un lanceur afin de concerver un profil ergonomique (fibomemo(k)), alors qu’un second paramètre servant à mémoriser le résultat des calculs est nécessaire.

from typing import Dict, Callable

def fiborec(n: int) -> int:
    def _fiborec(n: int, lvl: int) -> int: #lvl: pour debug
        global cplx
        global debug
        cplx += 1
        if debug: print(" " * lvl * 2 + "Fibonacci(" + str(n) + ")")    #debug
        return n if n <= 1 else _fiborec(n-1, lvl+1) + _fiborec(n-2, lvl+1)
    return _fiborec(n, 0)

def fibomemo(n: int) -> int:
    def _fibomemo(n: int, lvl: int, mem: Dict) -> int: #lvl: pour debug
        global cplx
        global debug
        if n in mem.keys():
            r = mem[n]
        else:
            cplx += 1
            if debug: print(" " * lvl * 2 + "Fibonacci(" + str(n) + ")")    #debug
            r = n if n <= 1 else _fibomemo(n-1, lvl+1, mem) +  _fibomemo(n-2, lvl+1, mem)
            mem[n] = r
        return r
    return _fibomemo(n, 0, {})

def fiboite(n: int) -> int:
    global cplx
    global debug
    a, b = 0, 1
    if debug: print("Fibonacci(0)") #debug
    cplx += 1 #Fibonacci(0)
    for i in range(n):
        if debug: print("Fibonacci(" + str(i+1) + ")")  #debug
        cplx += 1
        c = a + b
        a = b
        b = c
    return a

def suitefibo(n: int):
    global debug
    _debug = debug  #enregistre l'état
    debug = False
    for i in range(1, n + 1):
        run(i, fiboite)
    debug = _debug  #restore l'état

debug = True
def run(n: int, fun: Callable[[int], int]):
    global cplx
    cplx = 0
    fibo = fun(n)
    print("Fibo(" + str(n) + ") = " + str(fibo))
    if debug: print("Complexité : " + str(cplx))

Afficher la suite de fibonacci avec l’instruction suitefibo(10). Observer que chaque terme est la somme des deux termes précédents (fibo(4) = fibo(3) + fibo(2)).

La fonction run sert d’enveloppe pour afficher le résultat et la complexité en temps (de calcul) ; elle s’utilise de la façon suivante : run(5, fiborec) ou run(10, fiboite)…

Analyser la pile des appels de fonction pour la fonction fiborec.