Récurrences de complexité usuelles

9.5.1 Les récurrences T(n) = T(n − 1) + O(n^p)

Ces récurrences correspondent à un algorithme {A} dont l’accomplissement au rang {n} s’accompagne d’un coût spécifique {f(n)} (avec {f(n)\ge1}) et d’un seul appel du même algorithme {A} mais au rang {n-1}. On suppose ici que {f(n)=O(n^p)}, avec {p\in\mathbb{N}}.

Par exemple, le tri par sélection d’un tableau {v} de taille {n} consiste en les opérations suivantes, tant que le tableau considéré n’est pas réduit à un seul élément :

  • Parcourir la totalité du tableau, en notant la position du plus grand élément rencontré.
  • Échanger cet élément maximum avec le dernier élément du tableau {v}.
  • Recommencer avec le sous-tableau {v'} égal à {v} privé de son dernier élément.

On est bien ici en présence d’une récurrence {T(n)=T(n-1)+f(n)}, pour tout {n\ge1}, avec {T(1)=0}. Dans ce cas, {f(n)} peut s’écrire {f(n)=\lambda n+\mu} (une partie {\lambda n} proportionnelle à {n}, et traduisant le parcours du tableau à la recherche du maximum, et une partie constante {\mu} correspondant à l’échange final). On peut donc écrire {f(n)=O(n)}.

Dans le cas général, on suppose donc que {T(n)=T(n-1)+f(n)}, pour {n> n_0}, avec {T(n_0)\ge0} donné, et {f(n)\ge1}. On trouve immédiatement :

{\begin{array}{l}T(n)=T(n_0)+\sum_{k=n_0+1}^{n}f(k)\quad(n\ge n_0),\\[4pt]T(n)\sim\sum_{k=n_0+1}^{n}f(k).\end{array}}

On montre que si {f(n)=\Theta(n^p)}, alors {\sum\limits_{k=n_0+1}^{n}f(k)=\Theta(n^{p+1})}. Plus généralement, {f(n)=O(n^p)} implique {\sum\limits_{k=n_0+1}^{n}f(k)=O(n^{p+1})}.

On retiendra donc le résultat (avec {p\in\mathbb{N}^{\star}}) :

{T(n)=T(n-1)+O(n^p)\Rightarrow T(n)=O(n^{p+1}).}

On a notamment les deux cas particuliers importants :

{\begin{array}{l}T(n)=T(n-1)+O(1)\Rightarrow T(n)=O(n),\\[4pt]T(n)=T(n-1)+O(n)\Rightarrow T(n)=O(n^2).\end{array}}
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :