Complexité algorithmique/Introduction

Début de la boite de navigation du chapitre

Il est important, dans un souci de performance, d'évaluer la « qualité » d'un algorithme. Ce souci de performance peut être compris de deux manières différentes : soit en temps d'exécution du programme, soit en termes de stockage.

fin de la boite de navigation du chapitre

Notre première partie portera donc sur l'évaluation de la complexité en terme temporel.

Complexité temporelle

La complexité d'un algorithme donnée est le nombre d'opérations élémentaires nécessaires à son évaluation. On appelle opération élémentaire toute opération du type affectation, comparaison, opérations arithmétiques.

On s'intéresse alors au comportement asymptotique de cette mesure en fonction de la taille des données passées à l'algorithme. On définit donc des ordres de grandeur, nous permettant de classer des algorithmes en fonction de leur temps d'exécution. C'est le premier pas vers la recherche d'une meilleure performance, c'est-à-dire d'une amélioration de la complexité.

Pour déterminer la complexité, il y a trois mesures que l’on peut utiliser :

1. la durée maximale : $T_{max}(n)=\max\{{\text{Temps}}(d),|d|=n\}$ ;
2. la durée minimale : $T_{min}(n)=\min\{{\text{Temps}}(d),|d|=n\}$ ;
3. la durée moyenne : c’est la moyenne des temps d'exécution,

où ${\text{Temps}}(d)$ est le temps d'exécution de l'algorithme associée aux données d'entrée $d$.

Remarque. On utilisera alors la notation de Landau.

• $T(n)=O(f(n))$ signifie que la complexité $T(n)$ de l'algorithme étudié est majoré une quantité du type $Mf(n)$.
• De même, $T(n)=o(f(n))$ signifie que $T(n)$ a une complexité asymptotique négligeable devant $f(n)$ : ${\frac {T(n)}{f(n)}}\rightarrow 0$.

Il est important de comprendre que dire : "Tel algorithme est d'ordre o(x)", signifie qu’il aura une complexité inférieure ou égale à l’ordre x ET que x est le plus petit ordre supérieur à la complexité de notre algorithme.

Principaux ordres de grandeurs

• o(1) : Il s'agit de l’ordre de grandeur constant. C'est-à-dire que son exécution est indépendante des variables.

Début de l'exemple

Exemple

Début
Réaliser l'opération 4 × 5
Fin

Fin de l'exemple

• o(n) : Ordre de grandeur linéaire. Il dépend des variables de manière linéaire.

Début de l'exemple

Exemple

Début
Pour i de 1 à n faire
.....Afficher i
Fin pour
Fin

Fin de l'exemple

• o($n^{2}$) : C'est la complexité quadratique. Cela signifie que l'exécution sera liée à l'échelle du carré des variables.

Début de l'exemple

Exemple

Début
Pour i de 1 à n faire
.....Pour j de i à n faire
..........Afficher i*j
.....Fin pour
Fin pour
Fin

Fin de l'exemple

• o($n^{3}$) : C'est la complexité cubique. Cela signifie que l'exécution sera liée à l'échelle du cube des variables.

Début de l'exemple

Exemple

Début
Pour i de 1 à n faire
.....Pour j de i à n faire
..........Pour k de i à n faire
...............Afficher i*(j+k)
..........Fin pour
.....Fin pour
Fin pour
Fin

Fin de l'exemple

• o($2^{n}$) : C'est une complexité exponentielle: le temps d'exécution dépend de façon exponentielle de la taille des variables.
• o($n!$) : C'est un complexité factorielle.

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

De manière générale, le temps d'exécution est borné par une fonction f(n), n étant la "taille" des variables (cette taille peut être définie comme le plus grand nombre à calculer, ou le nombre de variables, etc.). Si la fonction f(n) est un polynôme (par exemple, 1, n, $n^{2}$, $n^{3}$), on dit que la complexité est polynomiale. Si f(n) est un logarithme, alors la complexité sera dite logarithmique (et le temps d'exécution sera plus rapide que pour une complexité polynomiale, lorsque les valeurs de n grandissent). Si f(n) contient n dans un exposant, alors la complexité sera dite exponentielle (et le temps d'exécution sera plus lent que pour une complexité polynomiale, lorsque les valeurs de n grandissent).

Complexité de stockage

La complexité en termes de stockage définit la taille en mémoire de l'algorithme ainsi que la taille des variables utilisées.

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?