Analyse des fonctions récursives
Introduction
L'analyse des algorithmes récursifs diffère de celle des algorithmes itératifs. Au lieu de compter le nombre d'itérations de boucles, on établit une relation de récurrence qui exprime le temps d'exécution en fonction de la taille de l'entrée.
Pour analyser une fonction récursive, on suit les étapes suivantes :
- Identifier le ou les cas de base (condition d'arrêt).
- Établir la relation de récurrence pour le cas général.
- Résoudre la récurrence pour obtenir la complexité asymptotique.
Relations de récurrence simples
Exemple 1 : Factorielle
int factorielle(int n) {
if (n <= 1)
return 1; // Cas de base
else
return n * factorielle(n - 1); // Appel récursif
}def factorielle(n):
if n <= 1:
return 1 # Cas de base
else:
return n * factorielle(n - 1) # Appel récursifAnalyse :
- Cas de base : \(T(1) = O(1)\)
- Cas général : \(T(n) = T(n-1) + O(1)\)
En développant :
\[ \begin{align*} T(n) &= T(n-1) + 1 \\ &= T(n-2) + 2 \\ &= \ldots \\ &= T(1) + (n-1) \\ &= 1 + (n-1) = n \end{align*} \]
Complexité : \(O(n)\)
Exemple 2 : Puissance
int puissance(int x, int n) {
if (n == 0)
return 1; // Cas de base
else
return x * puissance(x, n - 1); // Appel récursif
}def puissance(x, n):
if n == 0:
return 1 # Cas de base
else:
return x * puissance(x, n - 1) # Appel récursifAnalyse : Même structure que la factorielle → \(O(n)\)
Récurrences linéaires avec plusieurs appels
Exemple 3 : Fibonacci (récursif naïf)
int fibonacci(int n) {
if (n <= 1)
return n; // Cas de base
else
return fibonacci(n - 1) + fibonacci(n - 2); // Deux appels récursifs
}def fibonacci(n):
if n <= 1:
return n # Cas de base
else:
return fibonacci(n - 1) + fibonacci(n - 2) # Deux appels récursifsRelation de récurrence :
\[ T(n) = T(n-1) + T(n-2) + O(1) \]
Cette récurrence est plus difficile à résoudre. On peut montrer que :
\[ T(n) = O(2^n) \quad \text{(exponentiel)} \]
La version récursive naïve de Fibonacci est extrêmement inefficace (\(O(2^n)\)) car elle recalcule plusieurs fois les mêmes valeurs. Une version itérative ou avec mémoïsation est en \(O(n)\).
Récurrences de type "diviser pour régner"
Exemple 4 : Recherche dichotomique
int recherche_dichotomique(int tab[], int debut, int fin, int x) {
if (debut > fin)
return -1; // Cas de base : non trouvé
int milieu = (debut + fin) / 2;
if (tab[milieu] == x)
return milieu; // Cas de base : trouvé
else if (tab[milieu] < x)
return recherche_dichotomique(tab, milieu + 1, fin, x); // Appel sur moitié droite
else
return recherche_dichotomique(tab, debut, milieu - 1, x); // Appel sur moitié gauche
}def recherche_dichotomique(tab, debut, fin, x):
if debut > fin:
return -1 # Cas de base : non trouvé
milieu = (debut + fin) // 2
if tab[milieu] == x:
return milieu # Cas de base : trouvé
elif tab[milieu] < x:
return recherche_dichotomique(tab, milieu + 1, fin, x) # Appel sur moitié droite
else:
return recherche_dichotomique(tab, debut, milieu - 1, x) # Appel sur moitié gaucheRelation de récurrence :
\[ T(n) = T\left(\frac{n}{2}\right) + O(1) \]
Résolution :
\[ \begin{align*} T(n) &= T\left(\frac{n}{2}\right) + 1 \\ &= T\left(\frac{n}{4}\right) + 2 \\ &= \ldots \\ &= T(1) + \log_2 n \end{align*} \]
Complexité : \(O(\log n)\)
Exemple 5 : Tri fusion (Merge Sort)
void tri_fusion(int tab[], int debut, int fin) {
if (debut < fin) {
int milieu = (debut + fin) / 2;
tri_fusion(tab, debut, milieu); // Tri de la moitié gauche
tri_fusion(tab, milieu + 1, fin); // Tri de la moitié droite
fusionner(tab, debut, milieu, fin); // Fusion en O(n)
}
}def tri_fusion(tab):
if len(tab) <= 1:
return tab # Cas de base
milieu = len(tab) // 2
gauche = tri_fusion(tab[:milieu]) # Tri de la moitié gauche
droite = tri_fusion(tab[milieu:]) # Tri de la moitié droite
return fusion(gauche, droite) # Fusion en O(n)Relation de récurrence :
\[ T(n) = 2T\left(\frac{n}{2}\right) + O(n) \]
C'est une récurrence classique du type "diviser pour régner".
Par le théorème maître ou par développement :
\[ T(n) = O(n \log n) \]Tableau des récurrences courantes
| Type de récurrence | Exemple | Complexité |
|---|---|---|
| \(T(n) = T(n-1) + O(1)\) | Factorielle, puissance | \(O(n)\) |
| \(T(n) = T(n-1) + O(n)\) | Tri par sélection récursif | \(O(n^2)\) |
| \(T(n) = 2T(n-1) + O(1)\) | Fibonacci (naïf) | \(O(2^n)\) |
| \(T(n) = T(n/2) + O(1)\) | Recherche dichotomique | \(O(\log n)\) |
| \(T(n) = T(n/2) + O(n)\) | Cas particulier | \(O(n)\) |
| \(T(n) = 2T(n/2) + O(1)\) | Parcours d'arbre binaire | \(O(n)\) |
| \(T(n) = 2T(n/2) + O(n)\) | Tri fusion | \(O(n \log n)\) |
Méthodes de résolution des récurrences
1. Méthode par substitution (développement)
On développe la récurrence jusqu'à atteindre le cas de base.
Exemple : \(T(n) = T(n-1) + n\)
\[ \begin{align*} T(n) &= T(n-1) + n \\ &= T(n-2) + (n-1) + n \\ &= \ldots \\ &= T(1) + 2 + 3 + \ldots + n \\ &= O(1) + \frac{n(n+1)}{2} - 1 \\ &= O(n^2) \end{align*} \]
2. Théorème maître (Master Theorem)
Pour les récurrences de la forme \(T(n) = aT(n/b) + f(n)\) avec \(a \ge 1, b > 1\) :
| Cas | Condition | Complexité |
|---|---|---|
| Cas 1 | \(f(n) = O(n^{\log_b a - \varepsilon})\) | \(T(n) = \Theta(n^{\log_b a})\) |
| Cas 2 | \(f(n) = \Theta(n^{\log_b a} \log^k n)\) | \(T(n) = \Theta(n^{\log_b a} \log^{k+1} n)\) |
| Cas 3 | \(f(n) = \Omega(n^{\log_b a + \varepsilon})\) | \(T(n) = \Theta(f(n))\) |
Application au tri fusion :
\[ T(n) = 2T(n/2) + O(n) \]
Ici \(a = 2, b = 2, \log_b a = 1, f(n) = n = \Theta(n^{\log_b a} \log^0 n)\) → Cas 2 avec \(k = 0\)
Donc \(T(n) = \Theta(n \log n)\)
Complexité spatiale des fonctions récursives
Pour les fonctions récursives, il faut également prendre en compte l'espace utilisé par la pile d'appels (stack).
La complexité spatiale d'une fonction récursive est la somme de :
- L'espace utilisé par les variables locales à chaque appel.
- L'espace de la pile d'appels (profondeur de récursion).
Exemple 6 : Factorielle
- Profondeur de récursion : \(n\) appels imbriqués.
- Espace par appel : constant (\(O(1)\)).
- Complexité spatiale totale : \(O(n)\)
Exemple 7 : Recherche dichotomique
- Profondeur de récursion : \(\log n\) appels imbriqués.
- Espace par appel : constant (\(O(1)\)).
- Complexité spatiale totale : \(O(\log n)\)
Exemple 8 : Tri fusion
- Profondeur de récursion : \(\log n\) appels imbriqués.
- Espace par appel : constant (hors tableaux temporaires).
- Mais : la fusion nécessite un tableau temporaire de taille \(O(n)\) qui domine.
- Complexité spatiale totale : \(O(n)\)
Récapitulatif des exemples
| Algorithme | Récurrence | Complexité temporelle | Complexité spatiale |
|---|---|---|---|
| Factorielle | \(T(n) = T(n-1) + O(1)\) | \(O(n)\) | \(O(n)\) |
| Fibonacci naïf | \(T(n) = T(n-1) + T(n-2) + O(1)\) | \(O(2^n)\) | \(O(n)\) |
| Recherche dichotomique | \(T(n) = T(n/2) + O(1)\) | \(O(\log n)\) | \(O(\log n)\) |
| Tri fusion | \(T(n) = 2T(n/2) + O(n)\) | \(O(n \log n)\) | \(O(n)\) |
| Parcours d'arbre binaire | \(T(n) = 2T(n/2) + O(1)\) | \(O(n)\) | \(O(\log n)\) (hauteur) |
L'analyse des fonctions récursives repose sur l'établissement et la résolution de relations de récurrence.
- Cas de base : condition d'arrêt de la récursion.
- Relation de récurrence : exprime \(T(n)\) en fonction de \(T\) pour des entrées plus petites.
- Méthodes de résolution : substitution, théorème maître, arbre de récursion.
- Complexité spatiale : inclut la pile d'appels (profondeur de récursion).
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.