Chapitre 3

Complexité des algorithmes

3.1 Introduction

Le temps d’exécution d’un algorithme dépend des facteurs suivants :

– Les données utilisées par le programme,
– La qualité du compilateur (langage utilisé),
– La machine utilisée (vitesse, mémoire,. . .),
– La complexité de l’algorithme lui-même,
On cherche à mesurer la complexité d’un algorithme indépendamment de la machine et
du langage utilisés, c-à-d uniquement en fonction de la taille des données n que l’algorithme
doit traiter. Par exemple, dans le cas de tri d’un tableau, n est le nombre d’éléments du
tableau, et dans le cas de calcul d’un terme d’une suite n est l’indice du terme, ...etc.

3.2 O-notation

Soit la fonction T (n) qui représente l’évolution du temps d’exécution d’un programme
P en fonction du nombre de données n.
Par exemple :

T (n) = cn2

Où c est une constante non spécifiée qui représente la vitesse de la machine, les per-
formances du langage, ...etc. On dit dans l’exemple précédent que la complexité de P est
O(n2 ). Cela veut dire qu’il existe une constante c positive tel que pour n suffisamment
grand on a :
T (n)  cn2

17
 Cette notation donne une majoration du nombre d’opérations exécutées (temps d’exé-
cution) par le programme P . Un programme dont la complexité est O(f (n)) est un pro-
gramme qui a f (n) comme fonction de croissance du temps d’exécution.

3.3 Règles de calcul de la complexité d’un algorithme

3.3.1 La complexité d’une instruction élémentaire

Une opération élémentaire est une opération dont le temps d’exécution est indépendant
de la taille n des données tel que l’affectation, la lecture, l’écriture, la comparaison ...etc.

La complexité d’une instruction élémentaire est O(1)

3.3.2 La multiplication par une constante

O(c ⇤ f (n)) = O(f (n))

Exemple :
3
O( n4 ) = O(n3 )

3.3.3 La complexité d’une séquence de deux modules

La complexité d’une séquence de deux modules M1 de complexité O(f (n)) et M2

de complexité O(g(n)) est égale à la plus grande des complexité des deux modules :
O(max(f (n), g(n))).

O(f (n)) + O(g(n)) = O(max(f (n), (g(n))

3.3.4 La complexité d’une conditionnelle

La complexité d’une conditionnelle

Si (Cond) Alors
M1 ;
Sinon
M2 ;
Fin Si;

18
 est le max entre les complexités de l’évaluation de <Cond>, M1 et M2 .

Si (<Cond> [O(h(n))] ) Alors

M1 [O(f (n))]
Sinon
M2 [O(g(n))]
Fin Si;

La complexité de la conditionnelle est : M ax {O(h(n)), O(f (n)), O(g(n))}

3.3.5 La complexité d’une boucle

La complexité d’une boucle est égale à la somme sur toutes les itérations de la com-
plexité du corps de la boucle.

Tant que (<Condition> [O(h(n))]) faire

[m fois]
P ; [O(f (n))]
Fin TQ;

Pm
La complexité de la boucle est : M ax(h(n), f (n)) où m est le nombre d’itérations
exécutées par la boucle.

19
Exemple 1 :

Algorithme Recherche;
Var T : tableau[1..n] de entier ;
x,i : entier ;
trouv : booleen ;
Début
Pour i de 1 à n faire
Pn
Lire (T[i]) ; O(1) O( 1 1) = O(n)
Fin Pour;

Lire(x) ; O(1)
Trouv faux ; O(1) O(1)
i 1; O(1) O(n)
Tant que (trouv=faux et i<=n [O(1)]) faire
Si (T[i]=x [O(1)]) Alors
Trouv vrai ; [O(1)] O(1) O(n)
Fin Si;
i i + 1 ; [O(1)]
Fin TQ;

Si (trouv=vrai [O(1)]) Alors

Ecrire (x,’existe’) [O(1)] O(1)
Sinon
Ecrire (x, ’n”existe pas’)[O(1)]
Fin Si;
Fin.

La complexité de l’algorithme est de O(n) + O(1) + O(n) + O(1) = O(n).

20
Exemple 2 : Soit le module suivant :

Pour i de 1 à n faire
Pn
[n fois O( i=1 n i))]
Pour j de i+1 à n faire
Pn i
[n i fois O( 1 1) = O(n i)]
Si (T[i] > T[j] [O(1)] ) Alors
tmp T[i] ; [O(1)]
T[i] T[j] ; [O(1)] O(1)
T[j] tmp ;[O(1)]
Fin Si;
Fin Pour;
Fin Pour;

Pn
La complexité = O( (n i) = O((n 1) + (n 2) . . . + 1)
n2
= O( n(n2 1) ) = O( 2
n
2) = O(n2 )

21
Exemple 3 : Recherche dichotomique

Algorithme RechercheDecho;
Var T : tableau[1..n] de entier ;
x,sup,inf,m : entier ;
trouv : booleen ;
Début
Lire(x) ; [O(1)]
Trouv faux ; [O(1)]
inf 1; [O(1) O(1)]
sup n; [O(1)]
Tant que (trouv=faux et inf<sup) faire
[log2 (n) fois]
m (inf + Sup ) div 2 ; [O(1)]
Si (T[m]=x [O(1)]) Alors
Trouv vrai [O(1)]
Sinon
Si (T[m]<x [O(1)]) Alors
inf m +1 ; [ O(1) O(1) O(log2 (n))]
Sinon
Sup m - 1 ; [O(1)]
Fin Si;
Fin Si;
Fin TQ;

Si (trouv=vrai [O(1)]) Alors

Ecrire (x,’existe’) ; [O(1)] O(1)
Sinon
Ecrire (x, ’n’existe pas’) ; [O(1)]
Fin Si;
Fin.

La complexité de l’algorithme est de :

22
 O(1) + O(log2 (n)) + O(1) = O(log2 (n)) = O(log(n)).

3.4 Complexité des algorithmes récursifs

La complexité d’un algorithme récursif se fait par la résolution d’une équation de ré-
currence en éliminant la récurrence par substitution de proche en proche.
Exemple
Soit la fonction récursive suivante :

Fonction Fact( n : entier) : entier;

Début
Si (n <= 1 [O(1)] ) Alors
Fact 1 [O(1)]
Sinon
Fact n * Fact(n - 1) [O(1)]
Fin Si;
Fin;

Posons T (n) le temps d’exécution nécessaire pour un appel à F act(n), T (n) est le
maximum entre :
– la complexité du test n  1 qui est en O(1),
– la complexité de : Fact 1 qui est aussi en O(1),
– la complexité de : Fact n*Fact(n - 1) dont le temps d’exécution dépend de T (n 1)
(pour le calcul de Fact(n - 1))
On peut donc écrire que :

8
< a si n <= 1
T (n) =
: b + T (n 1) sinon (si n > 1)
– La constante a englobe le temps du test (n <= 1) et le temps de l’affectation
(Fact 1)
– La constante b englobe :
* le temps du test (n <= 1),
* le temps de l’opération * entre n et le résultat de F act(n 1),

23
 * et le temps de l’affectation finale (Fact ...)
T (n 1) (le temps nécessaire pour le calcul de F act(n 1) sera calculé (récursivement)
avec la même décomposition. Pour calculer la solution générale de cette équation, on peut
procéder par substitution :

T (n) = b + T (n 1)
= b + [b + T (n 2)]
= 2b + T (n 2)
= 2b + [b + T (n 3)]
= ...
= ib + T (n i)
= ib + [b + T (n i + 1)]
= ...
= (n 1)b + T (n n + 1) = nb b + T (1) = nb b+a
T (n) = nb b+a

Donc Fact est en O(n) car b est une constante positive.

3.5 Types de complexité algorithmique

1. T (n) = O(1), temps constant : temps d’exécution indépendant de la taille des données
à traiter.

2. T (n) = O(log(n)), temps logarithmique : on rencontre généralement une telle com-

plexité lorsque l’algorithme casse un gros problème en plusieurs petits, de sorte que
la résolution d’un seul de ces problèmes conduit à la solution du problème initial.

3. T (n) = O(n), temps linéaire : cette complexité est généralement obtenue lorsqu’un
travail en temps constant est effectué sur chaque donnée en entrée.

4. T (n) = O(n.log(n)) : l’algorithme scinde le problème en plusieurs sous-problèmes

plus petits qui sont résolus de manière indépendante. La résolution de l’ensemble de
ces problèmes plus petits apporte la solution du problème initial.

5. T (n) = O(n2 ), temps quadratique : apparaît notamment lorsque l’algorithme envi-

sage toutes les paires de données parmi les n entrées (ex. deux boucles imbriquées)
Remarque : O(n3 ) temps cubique

6. T (n) = O(2n ), temps exponentiel : souvent le résultat de recherche brutale d’une

solution.

24