Complexité des programmes

Cours · algorithmique (école d'ingénieur), chapitre 10 · école d'ingénieur, informatique · le début du chapitre, la suite sur Adloun

Objectifs du chapitre

Exprimer le temps de calcul d'un programme en fonction de la taille du problème, dans le pire cas.
Connaître les notations $O$ , $Ω$ et $Θ$ et les principales classes de complexité.
Savoir compter : boucles simples, boucles imbriquées, sommes, fonctions récursives.
Retrouver la complexité des programmes de programmation dynamique de la première partie.

Dans la première partie, nous avons souvent conclu un calcul par une phrase comme « le temps de calcul est de la forme $α n C + β$ ». Ce chapitre précise ce que cela veut dire, et pourquoi c'est la bonne façon de comparer des algorithmes.

10.1 Mesurer un algorithme, pas une machine

Le temps d'exécution d'un programme, mesuré en secondes, dépend de beaucoup de choses : la machine, le langage, le compilateur, la charge du système… et bien sûr les données. Pour comparer des algorithmes, on fait abstraction de la machine.

Définition 10.1Taille d'un problème

La taille d'une instance d'un problème est un (ou plusieurs) entier(s) qui mesure(nt) la quantité de données : le nombre $n$ de cases d'un tableau, le nombre $n$ d'objets et la contenance $C$ d'un sac, le nombre $n$ de sommets et $m$ d'arcs d'un graphe, le nombre de chiffres d'un entier…

On suppose que chaque instruction élémentaire (affectation, comparaison, opération arithmétique sur des int, accès à une case de tableau, appel de fonction) s'exécute en un temps borné par une constante. Le temps de calcul est alors proportionnel au nombre d'instructions élémentaires exécutées.

Définition 10.2Complexité dans le pire cas

Le temps de calcul dans le pire cas d'un programme est la fonction $t (n)$ qui, à chaque taille $n$ , associe le plus grand temps de calcul du programme parmi toutes les instances de taille $n$ .

La complexité du programme est la forme du terme dominant de $t (n)$ , constantes multiplicatives oubliées.

Exemple 10.3tri par insertion

Le tri par insertion (chapitre 14) d'un tableau de $n$ cases a, dans le pire cas (tableau trié à l'envers), un temps de calcul de la forme

$t (n) = α n^{2} + β n + γ, α > 0.$

Pour $n$ grand, $β n$ et $γ$ sont négligeables devant $α n^{2}$ : le terme dominant est $α n^{2}$ . On dit que la complexité est quadratique, et l'on écrit qu'elle est en $Θ (n^{2})$ .

Pourquoi le pire cas ? Parce qu'il donne une garantie : quelles que soient les données, le programme ne sera jamais plus lent. Le cas moyen est parfois plus représentatif (chapitre 14, tri rapide), mais il suppose une hypothèse sur la distribution des données, et il est plus difficile à calculer.

Attention

Le pire cas est le pire à taille $n$ fixée. Dire « le pire cas est $n = 1 0^{6}$ » n'a aucun sens : on cherche, pour chaque $n$ , la plus mauvaise instance de taille $n$ .

10.2 Les notations $O$ , $Ω$ et $Θ$

Les fonctions considérées vont des entiers naturels dans les réels positifs.

Définition 10.4Notations asymptotiques

Soient $f$ et $g$ deux fonctions de $N$ dans $R_{+}$ .

$f \in O (g)$ s'il existe une constante $c > 0$ et un rang $n_{0}$ tels que $\forall n \geq n_{0}, f (n) \leq c g (n)$ ( $f$ croît au plus comme $g$ ) ;
$f \in Ω (g)$ s'il existe $c > 0$ et $n_{0}$ tels que $\forall n \geq n_{0}, f (n) \geq c g (n)$ ( $f$ croît au moins comme $g$ ) ;
$f \in Θ (g)$ si $f \in O (g)$ et $f \in Ω (g)$ : il existe $c_{1}, c_{2} > 0$ et $n_{0}$ tels que $\forall n \geq n_{0}, c_{1} g (n) \leq f (n) \leq c_{2} g (n)$ ( $f$ croît exactement comme $g$ ).

L'usage est d'écrire $f = O (g)$ plutôt que $f \in O (g)$ , c'est un abus d'écriture.

Exemple 10.5un calcul de

Θ

Montrons que $t (n) = 3 n^{2} + 5 n + 7$ est en $Θ (n^{2})$ .

Pour tout $n \geq 1$ : $t (n) \leq 3 n^{2} + 5 n^{2} + 7 n^{2} = 15 n^{2}$ . Donc $t \in O (n^{2})$ avec $c = 15$ , $n_{0} = 1$ .
Pour tout $n \geq 0$ : $t (n) \geq 3 n^{2}$ . Donc $t \in Ω (n^{2})$ avec $c = 3$ .

Proposition 10.6Règles de calcul

Un polynôme de degré $d$ à coefficient dominant strictement positif est en $Θ (n^{d})$ .
Les constantes multiplicatives disparaissent : $Θ (α f) = Θ (f)$ pour $α > 0$ .
Somme : $Θ (f) + Θ (g) = Θ (max (f, g))$ . C'est la règle « le terme dominant l'emporte ».
Produit : $Θ (f) \times Θ (g) = Θ (f g)$ .
La base du logarithme est sans importance : $lo g_{a} n = \frac{l n n}{l n a}$ , donc $Θ (lo g_{a} n) = Θ (lo g_{b} n)$ . On écrit simplement $Θ (lo g n)$ .

Attention

$O$ n'est qu'une majoration. Il est vrai que la recherche séquentielle est en $O (n^{5})$ … mais c'est une information sans intérêt. Dans ce livre, nous donnons toujours la complexité exacte dans le pire cas, avec $Θ$ .

10.3 Les classes de complexité usuelles

Complexité	Nom	Exemple
$Θ (1)$	constante	accès à une case de tableau
$Θ (lo g n)$	logarithmique	recherche dichotomique (chapitre 12)
$Θ (n)$	linéaire	maximum d'un tableau, Zébulon
$Θ (n lo g n)$	quasi-linéaire	tri fusion (chapitre 14)
$Θ (n^{2})$	quadratique	tri par insertion
$Θ (n^{3})$	cubique	arbre binaire de recherche de coût minimum
$Θ (2^{n})$	exponentielle	énumération de tous les sous-ensembles

La suite du cours est sur Adloun

Le chapitre en entier, formules et figures comprises, avec le tuteur, les fiches, les QCM et les exercices.

Lire la suite du cours

En accès libre, sans inscription.

Exercices corrigés de ce chapitre

Lire la suite du cours →

Complexité des programmes

Objectifs du chapitre

10.1 Mesurer un algorithme, pas une machine

Attention

10.2 Les notations O, Ω et Θ

Attention

10.3 Les classes de complexité usuelles

10.2 Les notations $O$ , $Ω$ et $Θ$