Algorithmique : analyser un algorithme récursif

Relations de récurrence, arbre de récursion, théorème général

Claire Borrelli

2023-11-21

Table of contents

• 1. Poser une relation de récurrence
• 2. La méthode de l’arbre de récursion
• 3. La méthode de substitution
• 4. Le théorème général (Master Theorem)
• 5. Vérification empirique

Plan

1. Poser une relation de récurrence
2. Méthode de l’arbre de récursion
3. Méthode de substitution
4. Le théorème général (Master Theorem)
5. Vérification empirique en Python

1. Poser une relation de récurrence

Exemple fil rouge : le tri fusion

Le tri fusion (merge sort) divise la liste en deux moitiés, trie chaque moitié récursivement, puis fusionne les deux résultats triés.

def fusionner(gauche, droite):
    resultat = []
    i = j = 0
    while i < len(gauche) and j < len(droite):
        if gauche[i] <= droite[j]:
            resultat.append(gauche[i]); i += 1
        else:
            resultat.append(droite[j]); j += 1
    return resultat + gauche[i:] + droite[j:]

def tri_fusion(liste):
    if len(liste) <= 1:
        return liste
    milieu = len(liste) // 2
    gauche = tri_fusion(liste[:milieu])
    droite = tri_fusion(liste[milieu:])
    return fusionner(gauche, droite)

tri_fusion([5, 3, 8, 2, 9, 1])

[1, 2, 3, 5, 8, 9]

Traduire l’algorithme en récurrence

Notons \(T(n)\) le temps d’exécution sur une entrée de taille \(n\).

• Deux appels récursifs sur des sous-listes de taille \(n/2\) : coût \(2 \cdot T(n/2)\)
• La fusion de deux listes triées de taille totale \(n\) coûte \(\Theta(n)\)

\[T(n) = 2\,T\!\left(\frac{n}{2}\right) + \Theta(n)\]

Forme générale — un algorithme qui découpe son entrée en \(a\) sous-problèmes de taille \(n/b\), plus un travail non récursif \(f(n)\) : \[T(n) = a\,T\!\left(\frac{n}{b}\right) + f(n)\]

2. La méthode de l’arbre de récursion

Dérouler l’arbre

À chaque niveau de récursion, on double le nombre de sous-problèmes et on divise leur taille par deux.

Niveau	Nb de sous-problèmes	Taille de chacun	Coût du niveau
0	1	\(n\)	\(cn\)
1	2	\(n/2\)	\(2 \cdot c(n/2) = cn\)
2	4	\(n/4\)	\(4 \cdot c(n/4) = cn\)
…	…	…	…
\(\log_2 n\)	\(n\)	\(1\)	\(cn\)

Il y a \(\log_2 n + 1\) niveaux, chacun coûtant \(\Theta(n)\) :

\[T(n) = \Theta(n) \times \Theta(\log_2 n) = \Theta(n \log_2 n)\]

Ce que donne l’arbre — et ses limites

L’arbre de récursion donne une intuition rapide et une hypothèse sur la complexité — mais ce n’est pas, à proprement parler, une preuve rigoureuse. Pour prouver le résultat formellement, on vérifie l’hypothèse par récurrence (substitution) — ou on utilise le théorème général quand il s’applique.

3. La méthode de substitution

Principe : deviner puis vérifier

1. On devine une borne asymptotique (souvent suggérée par l’arbre de récursion)
2. On la vérifie par récurrence mathématique (cas de base + hérédité)

Exemple : vérifier \(T(n) = O(n \log_2 n)\)

Pour \(T(n) = 2T(\lfloor n/2 \rfloor) + n\), on veut montrer \(T(n) \le C\, n \log_2 n\) pour une constante \(C\) bien choisie.

Hérédité — en supposant l’hypothèse vraie pour \(\lfloor n/2 \rfloor\) :

\[T(n) = 2T(\lfloor n/2 \rfloor) + n \le 2C\left\lfloor\frac{n}{2}\right\rfloor\log_2\left(\frac{n}{2}\right) + n\] \[\le C\,n\left(\log_2 n - 1\right) + n = C\,n\log_2 n - (C - 1)n \le C\,n\log_2 n \quad \text{si } C \ge 1\]

Avec un cas de base vérifié séparément, on conclut \(T(n) = O(n\log_2 n)\).

Un piège classique

Une erreur fréquente : appliquer la définition de \(O(\cdot)\) à l’intérieur du raisonnement par récurrence, en gardant la même constante à chaque étape sans vérifier qu’elle reste valable — ce qui peut donner une conclusion fausse.

Note

Il faut fixer une constante unique, valable pour tous les \(n\) à partir d’un certain rang — pas une constante qui varie implicitement à chaque niveau de récursion.

4. Le théorème général (Master Theorem)

Énoncé

Pour une récurrence de la forme \(T(n) = a\,T(n/b) + f(n)\) avec \(a \ge 1\), \(b > 1\), on compare \(f(n)\) à \(n^{\log_b a}\) :

1. Si \(f(n) = O(n^{\log_b a - \varepsilon})\) pour un \(\varepsilon > 0\) : \(T(n) = \Theta(n^{\log_b a})\) (la récursion domine)
2. Si \(f(n) = \Theta(n^{\log_b a})\) : \(T(n) = \Theta(n^{\log_b a} \log n)\) (équilibre)
3. Si \(f(n) = \Omega(n^{\log_b a + \varepsilon})\) (+ condition de régularité) : \(T(n) = \Theta(f(n))\) (le travail non récursif domine)

Application 1 : le tri fusion

\[T(n) = 2T(n/2) + \Theta(n)\]

\(a = 2\), \(b = 2\), donc \(n^{\log_b a} = n^{\log_2 2} = n^1 = n\).

\(f(n) = \Theta(n) = \Theta(n^{\log_b a})\) → cas 2.

\[T(n) = \Theta(n \log n)\]

Cohérent avec le résultat obtenu par l’arbre de récursion.

Application 2 : la recherche dichotomique

La recherche dichotomique (binary search) divise l’espace de recherche en deux à chaque étape, avec un travail constant à chaque niveau :

\[T(n) = T(n/2) + \Theta(1)\]

\(a = 1\), \(b = 2\), donc \(n^{\log_b a} = n^0 = 1\). \(f(n) = \Theta(1) = \Theta(n^{\log_b a})\) → cas 2.

\[T(n) = \Theta(\log n)\]

def recherche_dichotomique(liste_triee, cible):
    gauche, droite = 0, len(liste_triee) - 1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if liste_triee[milieu] == cible:
            return milieu
        elif liste_triee[milieu] < cible:
            gauche = milieu + 1
        else:
            droite = milieu - 1
    return -1

recherche_dichotomique(list(range(0, 1000, 2)), 250)

125

Limites du théorème

• Ne s’applique qu’à des récurrences de cette forme précise (sous-problèmes de même taille)
• Ne couvre pas les cas où \(f(n)\) n’est ni polynomialement plus petite, ni polynomialement plus grande que \(n^{\log_b a}\)
• Dans ces cas : retour à l’arbre de récursion ou à la substitution

5. Vérification empirique

Compter les opérations réellement effectuées

Vérifions que le tri fusion fait bien de l’ordre de \(n \log_2 n\) comparaisons, contre \(n^2\) pour un tri par insertion.

import math
import matplotlib.pyplot as plt
import random

def tri_fusion_compte(liste, compteur):
    if len(liste) <= 1:
        return liste
    milieu = len(liste) // 2
    g = tri_fusion_compte(liste[:milieu], compteur)
    d = tri_fusion_compte(liste[milieu:], compteur)
    resultat, i, j = [], 0, 0
    while i < len(g) and j < len(d):
        compteur[0] += 1
        if g[i] <= d[j]:
            resultat.append(g[i]); i += 1
        else:
            resultat.append(d[j]); j += 1
    return resultat + g[i:] + d[j:]

tailles = [50, 100, 200, 400, 800, 1600]
comparaisons_reelles, borne_theorique = [], []

for n in tailles:
    liste = [random.random() for _ in range(n)]
    compteur = [0]
    tri_fusion_compte(liste, compteur)
    comparaisons_reelles.append(compteur[0])
    borne_theorique.append(n * math.log2(n))

Le résultat

plt.figure(figsize=(7, 4.5))
plt.plot(tailles, comparaisons_reelles, marker="o", label="Comparaisons réelles (tri fusion)")
plt.plot(tailles, borne_theorique, marker="o", linestyle="--", label="$n \\log_2 n$ (référence théorique)")
plt.xlabel("Taille de la liste (n)")
plt.ylabel("Nombre de comparaisons")
plt.legend()
plt.title("Tri fusion : comparaisons réelles vs borne théorique")
plt.tight_layout()
plt.show()

Les deux courbes évoluent au même rythme — cohérent avec \(T(n) = \Theta(n\log n)\) obtenu par le Master Theorem.

Conclusion

• Un algorithme récursif se traduit en une relation de récurrence \(T(n) = a\,T(n/b) + f(n)\)
• L’arbre de récursion donne rapidement une intuition du résultat
• La substitution (récurrence mathématique) permet de le prouver rigoureusement
• Le théorème général résout directement les cas les plus courants, en comparant \(f(n)\) à \(n^{\log_b a}\)
• Ces résultats théoriques se retrouvent empiriquement en comptant les opérations réellement exécutées