Adloun

Python (école d'ingénieur) · Chapitre 6 · Exercice

Complexité de Fibonacci récursif

Complexité algorithmique

Énoncé

On considère l'implémentation récursive naïve de Fibonacci :

def fibo(n):
    if n <= 1:
        return n
    return fibo(n-1) + fibo(n-2)

Montrer que le nombre d'appels récursifs $C (n)$ vérifie $C (n) = C (n - 1) + C (n - 2) + 1$ .

En déduire que $C (n) = 2 F_{n + 1} - 1$ où $F_{n}$ est le $n$ -ième nombre de Fibonacci ( $F_{0} = 0$ , $F_{1} = 1$ ).

Déterminer la complexité asymptotique.

Corrigé

Relation de récurrence : Pour $n \geq 2$ , appeler fibo(n) nécessite 1 appel (l'appel lui-même) plus tous les appels engendrés par les deux sous-branches fibo(n-1) et fibo(n-2) : $C (n) = C (n - 1) + C (n - 2) + 1$ Pour les cas de base : $C (0) = 1$ et $C (1) = 1$ .

Preuve par récurrence de $C (n) = 2 F_{n + 1} - 1$ :

Base :

$n = 0$ : $C (0) = 1$ et $2 F_{1} - 1 = 2 (1) - 1 = 1$ . Ok.

$n = 1$ : $C (1) = 1$ et $2 F_{2} - 1 = 2 (1) - 1 = 1$ . Ok.

Hérédité : Supposons la relation vraie pour $n - 1$ et $n - 2$ . $C (n) = C (n - 1) + C (n - 2) + 1 = (2 F_{n} - 1) + (2 F_{n - 1} - 1) + 1$ $C (n) = 2 (F_{n} + F_{n - 1}) - 1 = 2 F_{n + 1} - 1$ La propriété est démontrée pour tout $n \geq 0$ .

Complexité asymptotique : Les nombres de Fibonacci grandissent de façon géométrique en fonction du nombre d'or $ϕ = \frac{1 + 5}{2} \approx 1.618$ . On a $F_{n} \sim \frac{ϕ ^{n}}{5}$ , donc : $C (n) = Θ (ϕ^{n})$ La complexité temporelle est exponentielle.

100 % gratuit

La suite du chapitre est sur Adloun

7 autres exercices corrigés dans ce chapitre, et 7 à chercher avec le tuteur
Les 2 QCM du chapitre, le premier sans compte
Le tuteur, qui guide pas à pas sans donner la réponse

Exercice suivant et tuteur

Sans compte : le cours et le premier QCM. Exercices et tuteur : inscription gratuite en 30 secondes, sans carte bancaire.

Le cours du chapitre · Tous les exercices du chapitre

Exercice suivant et tuteur →