Analyse de la complexité algorithmique

Analyse de la complexité algorithmique

1. Pourquoi mesurer la complexité ?

Pour comparer deux algorithmes résolvant le même problème, on ne mesure pas leur temps d'exécution en secondes (qui dépend de la machine, du langage, etc.) mais le nombre d'opérations élémentaires effectuées, en fonction de la taille $n$ de l'entrée. C'est la complexité temporelle. On définit de même la complexité spatiale (mémoire utilisée).

2. Notations de Landau : $O$, $\Omega$, $\Theta$

Soient $f,g:\mathbb{N}\to\mathbb{R}_+$. On dit :
- $f(n)=O(g(n))$ (« $f$ est dominée par $g$ ») s'il existe $c>0$ et $n_0$ tels que $f(n)\leq c\,g(n)$ pour tout $n\geq n_0$ — majoration asymptotique ;
- $f(n)=\Omega(g(n))$ s'il existe $c>0,n_0$ tels que $f(n)\geq c\,g(n)$ pour $n\geq n_0$ — minoration asymptotique ;
- $f(n)=\Theta(g(n))$ si $f(n)=O(g(n))$ et $f(n)=\Omega(g(n))$ — l'ordre de grandeur exact.

Exemple : $f(n)=3n^2+5n+2$. On a $f(n)=O(n^2)$ (car pour $n\geq1$, $3n^2+5n+2\leq10n^2$) et $f(n)=\Omega(n^2)$ (car $f(n)\geq3n^2$), donc $f(n)=\Theta(n^2)$ : l'algorithme est de complexité quadratique.

3. Classes de complexité usuelles

Par ordre croissant de coût (pour $n$ grand) : $O(1)$ (constant), $O(\log n)$ (logarithmique), $O(n)$ (linéaire), $O(n\log n)$ (quasi-linéaire), $O(n^2)$ (quadratique), $O(n^k)$ (polynomiale), $O(2^n)$ (exponentielle), $O(n!)$ (factorielle).

Exemple typique : la recherche dans un tableau trié par dichotomie est $O(\log n)$ ; le tri par insertion est $O(n^2)$ dans le pire cas ; le tri fusion est $O(n\log n)$.

4. Calcul de complexité : boucles et récursivité

Boucles simples : une boucle parcourant $n$ éléments une fois coûte $O(n)$. Deux boucles imbriquées, chacune de taille $n$, coûtent $O(n^2)$ (produit des tailles, dans le cas indépendant).

Récursivité — équation de récurrence. Pour un algorithme récursif qui divise le problème en $a$ sous-problèmes de taille $n/b$ chacun, avec un coût $f(n)$ pour combiner les résultats, la complexité $T(n)$ vérifie :

Théorème maître (cas simplifié, $f(n)=\Theta(n^d)$) : en posant $p=\log_b a$ :
- si $d<p$ : $T(n)=\Theta(n^p)$ ;
- si $d=p$ : $T(n)=\Theta(n^p\log n)$ ;
- si $d>p$ : $T(n)=\Theta(n^d)$.

Exemple — tri fusion : $a=2$ sous-tableaux, $b=2$ (taille $n/2$ chacun), fusion en $f(n)=\Theta(n)$ (donc $d=1$). On a $p=\log_2 2=1=d$, donc $T(n)=\Theta(n\log n)$.

Exemple — recherche dichotomique : $a=1$ sous-problème de taille $n/2$, coût de combinaison $f(n)=\Theta(1)$ (donc $d=0$). $p=\log_2 1=0=d$, donc $T(n)=\Theta(\log n)$.

5. Récursivité naïve : Fibonacci

Le calcul naïf de $\text{Fib}(n)$ par double récursion ($T(n)=T(n-1)+T(n-2)+O(1)$) a une complexité $\Theta(\varphi^n)$ où $\varphi=(1+\sqrt5)/2$ est le nombre d'or — exponentielle, car l'arbre des appels recalcule de nombreuses fois les mêmes sous-problèmes. La mémoïsation (stocker les résultats déjà calculés) ramène ce coût à $O(n)$ : c'est le principe de la programmation dynamique.

6. Pire cas, meilleur cas, cas moyen

On distingue généralement :
- la complexité dans le pire cas : borne valable pour toute entrée de taille $n$ (la plus utilisée en pratique, car elle garantit une performance) ;
- la complexité dans le meilleur cas : la plus petite complexité possible parmi les entrées de taille $n$ ;
- la complexité en moyenne : espérance sur une distribution donnée des entrées.

Exemple — tri rapide (quicksort) : $\Theta(n\log n)$ en moyenne, mais $\Theta(n^2)$ dans le pire cas (pivot systématiquement mal choisi, par exemple sur un tableau déjà trié avec un pivot toujours pris en première position).

7. Récapitulatif

|---|---|