Chapitre 10

Bases de l’analyse de complexité

d’algorithmes

Les discussions précédentes ont fait intervenir l’existence ou non d’algorithmes

pour résoudre un problème donné, mais en ignorant un aspect pourtant essentiel en
pratique : les ressources nécessaires à son exécution, c’est-à-dire par exemple le temps
ou la mémoire nécessaire sur la machine pour l’exécuter.
L’objectif du chapitre suivant est de se focaliser sur l’une des ressources : le temps
de calcul. Dans le chapitre qui suit, nous évoquerons d’autres ressources comme l’es-
pace mémoire. On pourrait parler du temps parallèle, c’est-à-dire du temps sur une
machine parallèle, etc.
Commençons toutefois par bien comprendre la différence entre le cadre des cha-
pitres qui suivent et les chapitres précédents : dans les chapitres précédents, on parlait
de calculabilité, c’est-à-dire que l’on se posait la question de l’existence (ou de la
non-existence) de solutions algorithmiques à des problèmes donnés. On va maintenant
parler de complexité : c’est-à-dire que l’on se focalise maintenant uniquement sur des
problèmes décidables, pour lesquels on connaît un algorithme. La question que l’on se
pose maintenant est de comprendre s’il existe un algorithme efficace.
Cela nous mène tout d’abord à préciser ce que l’on a envie d’appeler efficace, et
comment on mesure cette efficacité. Toutefois, avant, il faut que notre lecteur ait les
idées au clair sur ce que l’on appelle la complexité d’un algorithme, ou la complexité
d’un problème, ce qui n’est pas la même chose.

Remarque 10.1 Même si nous évoquons les complexités en moyenne dans ce chapitre,
nous n’en aurons pas besoin à aucun moment dans les chapitres qui suivent : nous
le faisons surtout pour expliquer pourquoi elles sont peu utilisées pour ces types de
problèmes.

1
2 CHAPITRE 10. BASES DE L’ANALYSE DE COMPLEXITÉ D’ALGORITHMES

10.1 Complexité d’un algorithme

On considère donc typiquement dans ce chapitre un problème P pour lequel on
connaît un algorithme A : cet algorithme, on sait qu’il est correct, et qu’il termine. Il
prend en entrée une donnée d, et produit un résultat en sortie A(d) en utilisant certaines
ressources (on ne parle donc plus que de problèmes décidables).

Exemple 10.1 Le problème P peut par exemple être celui de déterminer si un nombre
v est parmi une liste de n nombres.

Il est clair que l’on peut bien construire un algorithme A pour résoudre ce pro-
blème : par exemple,
– on utilise une variable res que l’on met à 0 ;
– on parcourt la liste, et pour chaque élément :
– on regarde si cet élément est le nombre v :
– si c’est le cas, alors on met la variable res à 1
– à l’issue de cette boucle, on retourne res.
Cet algorithme n’est pas le plus efficace que l’on puisse envisager. D’une part, on
pourrait s’arrêter dès que l’on a mis res à 1, puisqu’on connaît la réponse. D’autre
part, on peut clairement faire tout autrement, et utiliser par exemple une recherche par
dichotomie (un algorithme récursif), si l’on sait que la liste est triée.

10.1.1 Premières considérations

On mesure toujours l’efficacité, c’est-à-dire la complexité, d’un algorithme en terme
d’une mesure élémentaire µ à valeur entière : cela peut être le nombre d’instructions
effectuées, la taille de la mémoire utilisée, ou le nombre de comparaisons effectuées,
ou toute autre mesure.
Il faut simplement qu’étant donnée une entrée d, on sache clairement associer à l’al-
gorithme A sur l’entrée d, la valeur de cette mesure, notée µ(A, d) : par exemple, pour
un algorithme de tri qui fonctionne avec des comparaisons, si la mesure élémentaire
µ est le nombre de comparaisons effectuées, µ(A, d) est le nombre de comparaisons
effectuées sur l’entrée d (une liste d’entiers) par l’algorithme de tri A pour produire le
résultat A(d) (cette liste d’entiers triée).
La fonction µ(A, d) dépend de A, mais aussi de l’entrée d. La qualité d’un algo-
rithme A n’est donc pas un critère absolu, mais une fonction quantitative µ(A, .) des
données d’entrée vers les entiers.

10.1.2 Complexité d’un algorithme au pire cas

En pratique, pour pouvoir appréhender cette fonction, on cherche souvent à évaluer
cette complexité pour les entrées d’une certaine taille : il y a souvent une fonction
taille qui associe à chaque donnée d’entrée d, un entier taille(d), qui correspond à
un paramètre naturel. Par exemple, cette fonction peut être celle qui compte le nombre
d’éléments dans la liste pour un algorithme de tri, la taille d’une matrice pour le calcul
du déterminant, la somme des longueurs des listes pour un algorithme de concaténation.
10.1. COMPLEXITÉ D’UN ALGORITHME 3

Pour passer d’une fonction des données vers les entiers, à une fonction des entiers
(les tailles) vers les entiers, on considère alors la complexité au pire cas : la complexité
µ(A, n) de l’algorithme A sur les entrées de taille n est définie par

µ(A, n) = max µ(A, d).

d entrée avec taille(d)=n

Autrement dit, la complexité µ(A, n) est la complexité la pire sur les données de
taille n.
Par défaut, lorsqu’on parle de complexité d’algorithme en informatique, il s’agit de
complexité au pire cas, comme ci-dessus.
Si l’on ne sait pas plus sur les données, on ne peut guère faire plus que d’avoir cette
vision pessimiste des choses : cela revient à évaluer la complexité dans le pire des cas
(le meilleur des cas n’a pas souvent un sens profond, et dans ce contexte le pessimisme
est de loin plus significatif).

10.1.3 Complexité moyenne d’un algorithme

Pour pouvoir en dire plus, il faut en savoir plus sur les données. Par exemple,
qu’elles sont distribuées selon une certaine loi de probabilité.
Dans ce cas, on peut alors parler de complexité en moyenne : la complexité moyenne
µ(A, n) de l’algorithme A sur les entrées de taille n est définie par

µ(A, n) = E[µ(A, d)|d entrée avec taille(d) = n],

où E désigne l’espérance (la moyenne).

Si l’on préfère,
X
µ(A, n) = π(d)µ(A, d),
d entrée avec taille(d)=n

où π(d) désigne la probabilité d’avoir la donnée d parmi toutes les données de taille n.
En pratique, le pire cas est rarement atteint et l’analyse en moyenne peut sembler
plus séduisante.
Mais, d’une part, il est important de comprendre que l’on ne peut pas parler de
moyenne sans loi de probabilité (sans distribution) sur les entrées. Cela implique que
l’on connaisse d’autre part la distribution des données en entrée, ce qui est très sou-
vent délicat à estimer en pratique. Comment anticiper par exemple les listes qui seront
données à un algorithme de tri par exemple ?
On fait parfois l’hypothèse que les données sont équiprobables (lorsque cela a un
sens, comme lorsqu’on trie n nombres entre 1 et n et où l’on peut supposer que les
permutations en entrée sont équiprobables), mais cela est est parfois arbitraire, et pas
totalement justifiable.
Et enfin, comme nous allons le voir sur quelques exemples, les calculs de com-
plexité en moyenne sont plus délicats à mettre en œuvre.
4 CHAPITRE 10. BASES DE L’ANALYSE DE COMPLEXITÉ D’ALGORITHMES

10.2 Complexité d’un problème

On peut aussi parler de la complexité d’un problème : cela permet de discuter de
l’optimalité ou non d’un algorithme pour résoudre un problème donné.
On fixe un problème P : par exemple celui de trier une liste d’entiers. Un algorithme
A qui résout ce problème est un algorithme qui répond à la spécification du problème
P : pour chaque donnée d, il produit la réponse correcte A(d).
La complexité du problème P sur les entrées de taille n est définie par

µ(P, n) = inf max µ(A, d).

A algorithme qui résout P d entrée avec taille(d)=n

Autrement dit, on ne fait plus seulement varier les entrées de taille n, mais aussi
l’algorithme. On considère le meilleur algorithme qui résout le problème. Le meilleur
étant celui avec la meilleure complexité au sens de la définition précédente, et donc au
pire cas. C’est donc la complexité du meilleur algorithme au pire cas.
L’intérêt de cette définition est le suivant : si un algorithme A possède la complexité
µ(P, n), c’est-à-dire est tel que µ(A, n) = µ(P, n) pour tout n, alors cet algorithme
est clairement optimal. Tout autre algorithme est moins performant, par définition. Cela
permet donc de prouver qu’un algorithme est optimal.

10.3 Exemple : Calcul du maximum

Nous allons illustrer la discussion précédente par un exemple : le problème du
calcul du maximum. Ce problème est le suivant : on se donne en entrée une liste
d’entiers naturels e1 , e2 , · · · , en , avec n ≥ 1, et on cherche à déterminer en sortie
M = max1≤i≤n ei , c’est-à-dire le plus grand de ces entiers.

10.3.1 Complexité d’un premier algorithme

En considérant que l’entrée est rangée dans un tableau, la fonction Java suivante
résout le problème.
s t a t i c i n t max ( i n t T [ ] ) {
i n t l = T . l e n g t h −1;
int M = T[ l ] ;
l = l −1;
while ( l ≥ 0) {
i f (M < T [ l ] ) M = T [ l ] ;
l = l −1;
}
r e t u r n M;
}

Si notre mesure élémentaire µ correspond au nombre de comparaisons, nous en

faisons 2 par itération de la boucle, qui est exécutée n − 1 fois, plus 1 dernière du type
l ≥ 0 lorsque l vaut 0. Nous avons donc µ(A, n) = 2n − 1 pour cet algorithme A, où
10.3. EXEMPLE : CALCUL DU MAXIMUM 5

n est la taille de l’entrée, c’est-à-dire le nombre d’entiers dans la liste e1 , e2 , · · · , en .

Ce nombre est indépendant de la donnée d, et donc µ(A, n) = 2n − 1.
Par contre, si notre mesure élémentaire µ correspond au nombre d’affectations,
nous en faisons 3 avant la boucle while. Chaque itération de la boucle effectue soit 1
ou 2 affectations suivant le résultat du test M<T[l]. On a donc pour une entrée d de
taille n, n + 2 ≤ µ(A, d) ≤ 2n + 1 : la valeur minimum est atteinte pour une liste
ayant son maximum dans son dernier élément, et la valeur maximum pour une liste
sans répétition triée dans l’ordre décroissant. Cette fois µ(A, d) dépend de l’entrée d.
La complexité au pire cas est donnée par µ(A, n) = 2n.

10.3.2 Complexité d’un second algorithme

Si l’entrée est rangée dans une liste, définie par exemple par
class List {
int val ; / / L ’ élément
List next ; / / La s u i t e

L i s t ( i n t val , L i s t next ) {
this . val = val ; this . next = next ;
}
}

la fonction suivante résout le problème.

s t a t i c i n t max ( L i s t a ) {
int M = a . val ;
f o r ( a = a . n e x t ; a 6= n u l l ; a = a . next ) {
i f ( a . v a l > M)
M = a . val ;}
r e t u r n M;
}

Si notre mesure élémentaire µ correspond au nombre de comparaisons entre entiers

(nous ne comptons pas les comparaisons entre variables de type référence sur le type
List ) nous en faisons 1 par itération de la boucle, qui est exécutée n − 1 fois, soit au
total n − 1.
La complexité µ(A, n) de cet algorithme A sur les entrés de taille n est donc n − 1.

10.3.3 Complexité du problème

On peut se poser la question de savoir s’il est possible de faire moins de n − 1
telles comparaisons : la réponse est non, à condition de se limiter aux algorithmes
qui fonctionnent seulement par comparaisons 1 . En effet, cet algorithme est optimal en
nombre de comparaisons.
1. Si les entrées sont des entiers et que l’on s’autorise de l’arithmétique, il peut peut-être être possible de
limiter les comparaions. On ne discutera pas ce type d’algorithmes ici.
6 CHAPITRE 10. BASES DE L’ANALYSE DE COMPLEXITÉ D’ALGORITHMES

En effet, considérons la classe C des algorithmes qui résolvent le problème de la

recherche du maximum de n éléments en utilisant comme critère de décision les com-
paraisons entre éléments, avec les hypothèses plus haut.
Commençons par énoncer la propriété suivante : tout algorithme A de C est tel que
tout élément autre que le maximum est comparé au moins une fois avec un élément qui
lui est plus grand.
En effet, soit i0 le rang du maximum M retourné par l’algorithme sur une liste
L = e1 .e2 . · · · .en : ei0 = M = max1≤i≤n ei . Raisonnons par l’absurde : soit j0 6= i0
tel que ej0 ne soit pas comparé avec un élément plus grand que lui. L’élément ej0 n’a
donc pas été comparé avec ei0 le maximum.
Considérerons la liste L0 = e1 .e2 . · · · .ej0 −1 .M + 1.ej0 +1 . · · · .en obtenue à partir
de L en remplaçant l’élément d’indice j0 par M +1.
L’algorithme A effectuera exactement les mêmes comparaisons sur L et L0 , sans
comparer L0 [j0 ] avec L0 [i0 ] et donc retournera L0 [i0 ], ce qui est incorrect. D’où une
contradiction, qui prouve la propriété.
Il découle de la propriété qu’il n’est pas possible de déterminer le maximum de
n-éléments en moins de n − 1 comparaisons entre entiers. Autrement dit, la complexité
du problème P du calcul du maximum sur les entrées de taille n est µ(P, n) = n − 1.
L’algorithme précédent fonctionnant en n − 1 telles comparaisons, il est optimal
pour cette mesure de complexité.

10.3.4 Complexité de l’algorithme en moyenne

Si notre mesure élémentaire µ correspond au nombre d’affectations à l’intérieur de
la boucle for, on voit que ce nombre dépend de la donnée.
On peut s’intéresser à sa complexité en moyenne : il faut faire une hypothèse sur la
distribution des entrées. Supposons que les listes en entrée dont on cherche à calculer
le maximum sont des permutations de {1, 2, · · · , n}, et que les n! permutations sont
équiprobables.
On peut montrer [Sedgewick and Flajolet, 1996, Froidevaux et al., 1993] que la com-
plexité moyenne sur les entrées de taille n pour cette mesure élémentaire µ est alors
donnée par Hn , le nième nombre harmonique : Hn = 1 + 21 + 13 + · · · n1 . Hn est de
l’ordre de log n lorsque n tend vers l’infini.
Cependant, le calcul est technique, et serait laborieux dans le cadre seul de ce cours.
Simplifions, en nous intéressons à un problème encore plus simple : plutôt que de
rechercher le maximum dans la liste e1 , e2 , · · · , en , avec n ≥ 1, donnons nous une
liste d’entiers de {1, 2, . . . , k} et un entier 1 ≤ v ≤ k, et cherchons à déterminer s’il
existe un indice 1 ≤ i ≤ n avec ei = v.
L’algorithme suivant résout le problème.
s t a t i c boolean t r o u v e ( i n t [ ] T , i n t v ) {
f o r ( i n t i = 0 ; i < T . l e n g t h ; i ++)
i f ( T [ i ] == v )
return true ;
return f a l s e ;
}
10.4. ASYMPTOTIQUES 7

Sa complexité au pire cas en nombre d’instructions élémentaires est linéaire en n,

puisque la boucle est effectuée n fois dans le pire cas.
Observons que les listes en entrée sont des fonctions de {1, 2, . . . , n} dans {1, 2, . . . , k},
que l’on appellera tableau. Supposons que chacun des tableaux est choisi de façon
équiprobable.
Remarquons qu’il y a k n tableaux. Parmi ceux-ci, (k − 1)n ne contiennent pas
l’élément v et dans ce cas, l’algorithme procède à exactement n itérations. Dans le
cas contraire, l’entier est dans le tableau et sa première occurrence est alors i avec une
probabilité de
(k − 1)i−1
ki
et il faut alors procéder à i itérations. Au total, nous avons une complexité moyenne de
n
(k − 1)n X (k − 1)i−1
C= n
× n + ×i
k i=1
ki

Or
n
X 1 + xn (nx − n − 1)
∀x, ixi−1 =
i=1
(1 − x)2
Pn n+1
(il suffit pour établir ce résultat de dériver i=1 xi = 1−x 1−x ) et donc
n 
(k − 1)n (k − 1)n
   
n 1
C=n + k 1 − (1 + ) = k 1 − 1 −
kn kn k k

10.4 Asymptotiques
10.4.1 Complexités asymptotiques
On le voit sur l’exemple précédent, réaliser une étude précise et complète de com-
plexité est souvent fastidieux, et parfois difficile. Aussi, on s’intéresse en informatique
plutôt à l’ordre de grandeur (l’asymptotique) des complexités quand la taille n des
entrées devient très grande.

10.4.2 Notations de Landau

Comme il en est l’habitude en informatique, on travaille souvent à un ordre de
grandeur près, via les notations O. Rappelons les définitions suivantes :

Définition 10.1 (Notation O) Soient f et g deux fonctions f, g : N → R≥0 . On note

f (n) = O(g(n)) lorsqu’il existe des entiers c et n0 tel que pour tout n ≥ n0 ,

f (n) ≤ cg(n).

Intuitivement, cela signifie que f est inférieur à g à une constante multiplicative

près, pour les instances (données) de tailles suffisamment grandes.
De même on définit :
8 CHAPITRE 10. BASES DE L’ANALYSE DE COMPLEXITÉ D’ALGORITHMES

Définition 10.2 (Notations o, Ω, Θ) Soient f et g deux fonctions f, g : N → R≥0 .

– On note f (n) = o(g(n)) lorsque pour tout réel c, il existe un entier n0 tels que
pour tout n ≥ n0 ,
f (n) ≤ cg(n).
– On note f (n) = Ω(g(n)) lorsqu’il existe des entiers c et n0 tels que pour tout
n ≥ n0 ,
cg(n) ≤ f (n).
(on a dans ce cas g = O(f ))
– On note f (n) = Θ(g(n)) lorsque f (n) = O(g(n)) et f (n) = Ω(g(n)).

Exercice 10.1. Soient f et g deux fonctions telles que

f (n)
lim
n→∞ g(n)

existe et vaut un nombre c > 0. Prouver que f (n) = Θ(g(n)).

Exercice 10.2. Prouver :

– Si f = O(g) et g = O(h) alors f = O(h).
– Si f = Ω(g) et g = Ω(h) alors f = O(h).
– Si f = Θ(g) et g = Θ(h) alors f = Θ(h).

Exercice 10.3. Donner des exemples d’algorithmes respectivement de compléxité :

– linéaire
– O(n log n)
– cubique
– non-polynomial

Exercice 10.4. Supposons que l’on a des algorithmes avec les temps listés plus bas
(en supposant que ce sont des temps exacts). De combien est ralentit ces algorithmes
lorque l’on (a) double la taille de l’entrée, (b) augmente la taille de l’entrée de 1.
1. n2
2. n3
3. 100n2
4. n log n
5. 2n

10.5 Notes bibliographiques

Lectures conseillées Pour aller plus loin sur les notions évoquées dans ce chapitre,
nous suggérons la lecture du polycopié du cours INF421, ou de de l’ouvrage [Kleinberg and Tardos, 2005],
et en particulier de ses premiers chapitres.

Bibliographie Le texte de ce chapitre est repris du texte que nous avions écrit dans le
polycopié INF421. Il est inspiré de l’introduction de l’ouvrage [Kleinberg and Tardos, 2005].
L’analyse du problème du calcul du maximum, et de ses variations est basée sur [Froidevaux et al., 1993].
Index

(Ag , r, Ad ), voir arbre binaire 6|=, voir conséquence sémantique

(V, E), voir graphe o, voir notations de Landau, 8
(q, u, v), voir configuration d’une machine ⊂, voir partie d’un ensemble
de Turing ×, voir produit cartésien de deux ensembles
., voir concaténation `, voir démonstration, voir relation suc-
Ac , voir complémentaire cesseur entre configurations d’une
F (G/p), voir substitution machines de Turing
L(M ), voir langage accepté par une ma- ∨, voir disjonction
chine de Turing ∧, voir conjonction
⇔, voir double implication uqv, voir configuration d’une machine de
Ω, voir notations de Landau, 8 Turing
⇒, voir définition inductive / différentes hhM i, wi, voir codage d’une paire
notations d’une, voir implica- hM i, voir codage d’une machine de Tu-
tion ring
Σ, voir alphabet hmi, voir codage
Σ∗ , voir ensemble des mots sur un alpha- hφi, voir codage d’une formule
bet hw1 , w2 i, voir codage d’une paire
Θ, voir notations de Landau, 8
∩, voir intersection de deux ensembles algorithme, 2
∪, voir union de deux ensembles efficace, 1
, voir mot vide Arith, voir expressions arithmétiques
≡, voir équivalence entre formules, voir Arith0 , voir expressions arithmétiques pa-
équivalence entre problèmes renthésées
∃, voir quantificateur
∀, voir quantificateur calculabilité, 1
≤m , voir réduction codage
|w|, voir longueur d’un mot notation, voir h.i
≤, voir réduction d’une formule
E, 3 notation, voir hφi
A(d), 2 d’une machine de Turing
P(E), voir parties d’un ensemble notation, voir hM i
|=, voir conséquence sémantique d’une paire
µ(A, d), 2, voir mesure élémentaire notation, voir hhM i, wi, voir hw1 , w2 i
µ(A, n), 3, voir complexité d’un algo- complémentaire
rithme au pire cas, voir com- notation, voir Ac
plexité d’un algorithme en moyenne du problème de l’arrêt des machines
¬, voir négation de Turing

9
10 INDEX

notation , voir HALTING − PROBLEM notations

complétude de Landau, 7
RE-complétude, voir RE-complet
complexité, 1 partie
asymptotique d’un algorithme, 7 d’un ensemble
d’un algorithme, 3 notation, voir ⊂
au pire cas, 3 parties
en moyenne, 3 d’un ensemble
d’un problème, 4 notation, voir P(E)
concaténation problème, 2
notation, voir . de l’arrêt des machines de Turing
configuration d’une machine de Turing notation, voir HALTING − PROBLEM
notation, voir (q, u, v), voir uqv produit cartésien
de deux ensembles
décidable, 1 notation, voir ×
dichotomie, 2
R, voir décidable
efficace, voir algorithme RE, voir récursivement énumérable
équivalence recherche par dichotomie, 2
entre problèmes récusivement énumérable
notation, voir ≡ notation, voir RE
réduction
graphe notation, voir ≤, voir ≤m
notation, voir (V, E) relation successeur entre configurations d’une
machine de Turing
HALTING − PROBLEM, voir problème notation, voir `
de l’arrêt des machines de Tu- ressources, 1
ring
HALTING − PROBLEM, voir complé- temps de calcul, 1
mentaire du problème de l’arrêt
d’une machine de Turing union de deux ensembles
notation, voir ∪
intersection de deux ensembles
notation, voir ∩

langage
accepté par une machine de Turing
notation, voir L(M )
longueur d’un mot
notation, voir |w|

mémoire, 1
mesure élémentaire, 2
notation, voir µ(A, d)
mot
vide
notation, voir 
Bibliographie

[Froidevaux et al., 1993] Froidevaux, C., Gaudel, M., and Soria, M. (1993). Types de
donnees et algorithmes. Ediscience International.
[Kleinberg and Tardos, 2005] Kleinberg, J. and Tardos, E. (2005). Algorithm design.
Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA.
[Sedgewick and Flajolet, 1996] Sedgewick, R. and Flajolet, P. (1996). Introduction à
l’analyse d’algorithmes. International Thomson Publishing, FRANCE.

11