Substitution Method for Simple Recurrences

1. De l'algorithme récursif à la relation de récurrence

Analyser un algorithme récursif commence par la modélisation de son temps d'exécution. Le temps pour résoudre un problème de taille $n$, noté $T(n)$, est la somme du temps des appels récursifs sur des sous-problèmes plus petits et du travail effectué à l'étape courante.

Pour comprendre concrètement comment on établit une telle relation, nous allons analyser un premier algorithme très simple.

Ce processus est fondamental. Une relation de récurrence pour la complexité est toujours composée de deux parties :

• La relation récursive : Elle définit $T(n)$ en fonction de termes plus petits. Pour l'exemple de la vidéo, c'est $T(n)=T(n-1)+1$ pour $n>0$. Le terme $T(n-1)$ représente le coût de l'appel récursif, et le +1 (ou plus généralement +c pour une constante $c$) représente le travail constant effectué à chaque appel (condition, printf, etc.).
• Le cas de base : Il définit la valeur pour laquelle la récursion s'arrête. Ici, $T(0)=1$, car même l'appel qui ne fait rien consomme un temps constant.

Maintenant que nous avons notre équation, comment la "résoudre", c'est-à-dire trouver une forme non-récursive (une "forme close") pour $T(n)$ ?

2. Méthode de substitution par itérations (ou "télescopage")

La première approche pour résoudre une récurrence est intuitive. Elle consiste à "dérouler" la définition récursive plusieurs fois jusqu'à ce qu'un schéma général se dégage. Cette méthode est aussi connue sous les noms de back-substitution, plug-and-chug ou télescopage.

La méthode est donc :

1. Développer la récurrence sur plusieurs termes.
2. Identifier un motif général après $k$ substitutions.
3. Résoudre en fonction du cas de base pour trouver une forme close.

Pour $T(n)=T(n-1)+1$ avec $T(0)=1$, on a trouvé $T(n)=n+1$. La complexité est donc bien, comme notre intuition le suggérait, en $\Theta (n)$.

Cette méthode s'applique aussi lorsque le travail à chaque étape n'est pas constant. Considérons un algorithme dont le temps d'exécution est décrit par $T(n)=T(n-1)+n$. Cela pourrait correspondre à une fonction récursive qui contient une boucle for de 1 à n.

Le raisonnement est identique, mais les calculs sont un peu plus complexes. La somme qui apparaît ne sera plus une somme de constantes.

3. La méthode de substitution par preuve d'induction

La méthode par itérations est excellente pour deviner une solution. Cependant, pour une préparation à l'Agrégation, il est impératif de savoir prouver formellement que notre "supposition" est correcte. C'est ici qu'intervient la seconde facette de la méthode de substitution, telle que présentée dans les ouvrages de référence comme le Cormen.

La méthode se déroule en deux temps :

1. Deviner la forme de la solution (par exemple, en utilisant la méthode par itérations que nous venons de voir, ou simplement par intuition).
2. Prouver la solution par récurrence (induction mathématique) que cette forme est correcte, en déterminant les constantes nécessaires.

Appliquons cela à notre récurrence $T(n)=T(n-1)+c$ avec $T(1)=c$.

1. Devinette : Nous avons vu que la solution est $T(n)=cn$. Nous allons donc essayer de prouver que $T(n)=O(n)$. Formellement, nous voulons montrer qu'il existe une constante $k>0$ et un rang $n_0$ tels que pour tout $n\ge n_0$, $T(n)\le kn$.

2. Preuve par récurrence :

   • Hypothèse de récurrence $P(n)$ : $T(n)\le kn$.

   • Cas de base : Pour $n=1$, nous avons $T(1)=c$. L'hypothèse $T(1)\le k\cdot 1$ est vraie si nous choisissons $k\ge c$.

   • Cas inductif : Supposons que $P(n-1)$ est vraie pour $n-1\ge 1$, c'est-à-dire $T(n-1)\le k(n-1)$. Montrons que $P(n)$ est vraie.

     $$\begin{array}{rl}T(n)& =T(n-1)+c\\ & \le k(n-1)+c\text{(par hypotheˋse de reˊcurrence)}\\ & =kn-k+c\end{array}$$

     Nous voulons montrer que cette expression est inférieure ou égale à $kn$.

     $$kn-k+c\le kn$$

     Cette inégalité est vraie si $-k+c\le 0$, soit $k\ge c$.

   • Conclusion : Nous avons trouvé une condition sur $k$ ($k\ge c$) qui fonctionne à la fois pour le cas de base et pour le cas inductif. Nous pouvons donc choisir un tel $k$ (par exemple, $k=c$ si $c>0$), et la preuve est complète. Nous avons formellement démontré que $T(n)=O(n)$.

Cette démarche est plus rigoureuse et sera votre outil de prédilection pour les démonstrations formelles.

4. Exercice d'application

Mettons maintenant ces deux approches en synergie pour résoudre une récurrence légèrement plus complexe.

Problème : Soit la récurrence $T(n)=T(n-1)+n$ avec $T(0)=1$.

Étape 1 : Intuition par back-substitution
Regardez comment cette récurrence est résolue avec la méthode par itérations.

Comme le montre la vidéo, la solution est $T(n)=T(0)+{\sum }_{i=1}^{n}i=1+\frac{n(n+1)}{2}$. Cette expression est un polynôme de degré 2. La complexité est donc en $\Theta (n^2)$.

Étape 2 : Preuve formelle par induction

Maintenant que nous avons une excellente supposition ($T(n)=O(n^2)$), votre tâche est de le prouver formellement.

Exercice : Montrez que la solution de $T(n)=T(n-1)+n$ est $O(n^2)$. (Ceci correspond à l'exercice 4.3-1 du document didawiki.)

Votre démarche :

1. Objectif : Prouver qu'il existe des constantes $k>0$ et $n_0$ telles que $T(n)\le k{n}^2$ pour $n\ge n_0$.
2. Cas de base : Vérifiez pour $n=1$. On a $T(1)=T(0)+1=2$. L'inégalité $2\le k\cdot 1^2$ est vraie si $k\ge 2$.
3. Cas inductif :
   • Supposez $T(n-1)\le k(n-1{)}^2$ pour $n-1\ge n_0$.
   • Développez $T(n)=T(n-1)+n$.
   • Utilisez votre hypothèse et développez l'expression $(n-1{)}^2$.
   • Essayez de montrer que le résultat est $\le k{n}^2$. Vous devriez arriver à une condition de la forme $k{n}^2-2kn+k+n\le k{n}^2$, qui se simplifie en $n(1-2k)+k\le 0$.
   • Analysez cette dernière inégalité : si vous choisissez une constante $k$ suffisamment grande (par exemple $k\ge 1$), est-ce que cette condition est remplie pour tout $n\ge 1$ ? Vous constaterez que oui, car le terme en $-2kn$ dominera les autres.

Prenez le temps de rédiger cette preuve, c'est un excellent entraînement à la manipulation d'inégalités et au raisonnement par récurrence.

Conclusion

Aujourd'hui, nous avons jeté les bases de l'analyse des algorithmes récursifs. Nous avons appris à traduire un algorithme en relation de récurrence et à la résoudre par la méthode de substitution.

Points clés à retenir :

• La complexité d'un algorithme récursif est modélisée par une relation de récurrence.
• La méthode de substitution par itérations (télescopage) est une technique intuitive pour "deviner" la forme close d'une récurrence en la déroulant.
• La méthode de substitution par induction est la technique formelle pour prouver qu'une solution supposée est correcte. Elle s'articule en deux temps : deviner et prouver.
• Nous avons résolu $T(n)=T(n-1)+c⟹T(n)\in \Theta (n)$ et $T(n)=T(n-1)+n⟹T(n)\in \Theta (n^2)$.

Dans la prochaine leçon, nous passerons à une nouvelle famille de récurrences, celles issues des algorithmes de type "diviser pour régner", comme le tri fusion. Ces récurrences ont la forme $T(n)=aT(n/b)+f(n)$. Pour les résoudre, nous découvrirons un outil extrêmement puissant et rapide : le théorème maître (Master Theorem).