Optimisation de Fibonacci — exercice corrigé de Python (école d'ingénieur) (chapitre 6)

Optimisation de Fibonacci

Complexité algorithmique

Énoncé

Proposer trois implémentations du calcul du $n$ -ième terme de la suite de Fibonacci avec les complexités suivantes :

Récursive naïve ( $Θ (ϕ^{n})$ en temps, $Θ (n)$ en espace pile)

Récursive avec mémoïsation ( $Θ (n)$ en temps, $Θ (n)$ en espace)

Itérative ( $Θ (n)$ en temps, $Θ (1)$ en espace supplémentaire)

Corrigé

Voici les codes des trois versions :

# 1. Version récursive naïve
def fibo_naif(n):
    if n <= 1:
        return n
    return fibo_naif(n-1) + fibo_naif(n-2)

# 2. Version récursive avec mémoïsation (cache)
def fibo_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibo_memo(n-1, memo) + fibo_memo(n-2, memo)
    return memo[n]

# 3. Version itérative (optimale)
def fibo_iter(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a + b
    return b

Le tableau suivant récapitule les différences d'efficacité :

Version	Complexité Temporelle	Complexité Spatiale
Récursive naïve	$Θ (ϕ^{n})$	$Θ (n)$ (pile)
Mémoïsation	$Θ (n)$	$Θ (n)$ (dictionnaire)
Itérative	$Θ (n)$	$Θ (1)$ (deux variables)