Complexité algorithmique/Introduction

**Introduction**
Leçon : Complexité algorithmique

Chapitre n^o 1
Retour au	Sommaire
Chap. suiv. :	Complexité descriptive

En raison de limitations techniques, la typographie souhaitable du titre, « Complexité algorithmique : Introduction
Complexité algorithmique/Introduction », n'a pu être restituée correctement ci-dessus.

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.

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

Complexité temporelle[modifier | modifier le wikicode]

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 :

la durée maximale : $T_{max}(n)=\max\{{\text{Temps}}(d),|d|=n\}$ ;
la durée minimale : $T_{min}(n)=\min\{{\text{Temps}}(d),|d|=n\}$ ;
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[modifier | modifier le wikicode]

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

Exemple

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

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

Exemple

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

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

Exemple

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

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

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

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).