Algorithmique et Structures de 2020-2021 – Semestre 3 Université Constantine 2

Données

Université Abdelhamid Mehri – Constantine 2

2020-2021. Semestre 3

Algorithmique et Structures de Données (ASD)

– Cours –
Chapitre 02 : Notion de complexité algorithmique

Staff pédagogique
Nom Grade Faculté/Institut Adresse e-mail
BELALA Faiza Professeur Nouvelles Technologies [email protected]
HAMMOUD Djamila MCB Nouvelles Technologies Djamila.hammoud@univ-
constantine2.dz

Etudiants concernés
Faculté/Institut Département Année Spécialité
Nouvelles Technologies MI Licence 2

Objectifs du cours
Comparer théoriquement des algorithmes
Calculer le temps d'exécution théorique d'un algorithme simple
Identifier la difficulté de calcul du temps d'exécution d'un algorithme récursif

© Belala Faiza Page 1 sur 10

Algorithmique et Structures de 2020-2021 – Semestre 3 Université Constantine 2
Données

1. Introduction
Etant donné un problème à résoudre algorithmiquement, une des questions la plus immédiate est de
trouver un algorithme efficace, si possible. La question suivante est, bien sûr, de pouvoir décider
qu’un algorithme est meilleur qu’un autre ou que tous les autres. On pourrait penser que les
performances croissantes des ordinateurs permettent de négliger de plus en plus cet aspect des
choses.
Nous nous intéresserons, dans ce cours, à la comparaison théorique des algorithmes, tout en
supposant que les algorithmes à étudier sont (totalement) corrects. Sachant qu'un algorithme est
correct, lorsque pour chaque instance, il se termine en produisant la bonne sortie.

Sans entrer dans les détails mathématiques, le calcul de l’efficacité d’un algorithme (sa complexité
algorithmique) consiste en la recherche de deux quantités importantes:

1. La première quantité est l’évolution du nombre d’instructions de base en fonction de la

quantité de données à traiter (par exemple, pour un algorithme de tri, il s'agit du nombre de
données à trier.
2. La seconde quantité estimée est la quantité de mémoire nécessaire pour effectuer les calculs.

La complexité d'un algorithme ne devrait pas dépendre du temps d'exécution mesuré en secondes,
ce dernier dépend de la machine sur laquelle l'algorithme s'exécute, sa charge de travail, la vitesse
de son processeur, la vitesse d’accès aux données, l’exécution de l’algorithme (qui peut faire
intervenir le hasard) ou son organisation de la mémoire.

Le but de l’analyse de la complexité est limité dans ce module à l'évaluation en temps d'exécution
d'un algorithme. Autrement dit, déterminer un ordre de grandeur du temps nécessaire à l’exécution
du programme, indépendamment de l’ordinateur utilisé.

2. Complexité en temps
Définition :
On appelle complexité d’un algorithme A pour une donnée d de taille n la durée d’exécution de
l’algorithme A pour cette donnée : CoûtA(d)

On cherche à déterminer une mesure en temps exprimant la complexité intrinsèque des algorithmes
indépendamment de leur implémentation et non le temps d'exécution exact d'un algorithme donné.
On se donne pour réaliser cela:

1. Une mesure de taille de donnée : qui sera souvent définie cas par cas.

Exemple :
 Pour un problème de manipulation de matrices, on pourra prendre la dimension
maximale ou bien la somme, ou le produit des dimensions.
 Pour un problème de tri d’un tableau, on pourra prendre le nombre d’éléments à trier.

© Belala Faiza Page 2 sur 10

Algorithmique et Structures de 2020-2021 – Semestre 3 Université Constantine 2
Données

2. Une unité d’évaluation : on peut mettre en évidence une ou plusieurs opérations jugées
fondamentales au sens où le temps d’exécution d’un algorithme est toujours proportionnel
au nombre de ces opérations.

Exemple :
 Pour le problème de recherche d’un élément dans une table, l’unité pourra être la durée
d’exécution d’une instruction élémentaire (si on suppose que les instructions
élémentaires ont toutes le même temps d’exécution).
 On peut prendre comme unité (c’est le plus souvent) le coût d’une comparaison
d'élément recherché à un élément de la table.

Pour certains algorithmes, le temps exécution ne dépend pas, que de la taille des données; mais la
plupart du temps, la complexité varie aussi en fonction de la configuration ou la localité de la
donnée.

Les principales notions mathématiques dans le calcul du coût d’un algorithme précis sont
les notions de domination (notée θ(f(n)), « grand o »), où f est une fonction mathématique de n. n
est une variable désignant la quantité d’informations (en bits, en nombre d’enregistrements, etc.)
manipulée dans l’algorithme. En algorithmique, on s’intéresse bien souvent à des ordres de
grandeurs et non à des valeurs exactes.
On utilise très souvent la notation g = θ(f) pour dire que la fonction g est de l’ordre de f.

Définition :
Soient deux algorithmes A et B de complexité respectives f(n) et g(n), on dit que:
f = θ(g) si et seulement si il existe un entier n0 et c R+ tel que : n > n0, on a: f(n) < c*g(n)

On dit que f est dominée asymptotiquement par g.

Les ordres de grandeurs qu’on rencontre le plus souvent en algorithmique sont : Log(n), n 2, n3, n4,
nn, 2n, n
Le tableau ci-dessus indique le temps d'exécution de certains algorithmes selon leur comportement
et la taille des données n (on suppose que la durée d'une instruction élémentaire est de l'ordre de la
ns.
On voit donc que l’ordre de grandeur de l’algorithme utilisé va être le facteur prépondérant pour
déterminer quelle taille maximum du problème on pourra traiter dans un temps donné.
Un algorithme est dit :
 En temps constant si sa complexité dans le pire des cas est bornée par une constante.
 Linéaire (respectivement, linéairement borné) si sa complexité (dans le pire des cas) est en (n)
(respectivement, en θ (n)).
 Sub linéaire si sa complexité (dans le pire des cas) est en (log2(n) ), c.à.d. logarithmique
(respectivement, en θ (log2(n))).
 Quadratique si sa complexité (dans le pire des cas) est en (n2) (resp. en θ (n2)).
 Polynômial ou polynômialement borné, si sa complexité (dans le pire des cas) est en θ(np) pour
un certain p.
 Exponentiel si sa complexité est en θ(2n).

© Belala Faiza Page 3 sur 10

 Algorithmique et Structures de 2020-2021 – Semestre 3 Université Constantine 2
Données

Ordre de grandeur du temps nécessaire à l'exécution d'un algorithme d'un type de complexité

Temps Type de complexité Temps Temps Temps Temps pour Temps pour Exemple de
θ( ) pour n=5 pour n=10 pour n=10000 n=1000000 problème
n=1000
θ(1) Complexité 10 ns 10 ns 10 ns 10 ns 10 ns Accès tableaux
constante
θ(log(n)) Complexité 10 ns 10 ns 30 ns 40 ns 60 ns Dichotomie
logarithmique
θ(n ) Complexité 22 ns 32 ns 316 ns 1µs 10 µs
racinaire
θ(n) Complexité linéaire 50 ns 100 ns 10 µs 100µs 10ms Parcours de liste
Θ(nlog(n) ) Complexité quasi 50 ns 100 ns 10 µs 100,5µs 10050µs Triangulation de
linéaire Delaunay
θ(n2) Complexité 250 ns 1µs 625 µs 1s 2,8 heures Parcours de
quadratique tableaux de deux
(polynomiale) dimensions
θ(n3 ) Complexité cubique 1,25 µs 10 µs 10s 2,7 heures 316 ans Multiplication
(polynomiale) matricielle non
optimisée
θ(n! ) Complexité 1,2 µs 36ms astronomique astronomique Problème du
factorielle voyageur de
commerce (avec
une approche naive)
2n 1000µs 1014 astronomique astronomique
siècles

Un polynôme est de l'ordre de son degré. On distingues les fonctions linéaires (en θ(n) ), les
fonctions quadratiques (en θ(n2)) et les fonctions cubiques (en θ(n3)).
n
Les fonctions d'ordre exponentiel sont les fonctions en θ(a ) ou a >1.
Les fonctions d'ordre logarithmique sont les fonctions en θ(log(n)) (Remarquons que peu importe la
base du logarithme). Une classe intéressante d'algorithme est en nlog(n).

Comparaison de nlog(n) et de n 2.

3. Calcul de complexité
Déterminer la complexité d’un algorithme A revient à trouver un ordre de grandeur pour la fonction
coûtA(n) représentant le temps d’exécution de cet algorithme en fonction de la taille n des données
d’entrée et les opérations fondamentales.

Instruction simple

© Belala Faiza Page 4 sur 10

Algorithmique et Structures de 2020-2021 – Semestre 3 Université Constantine 2
Données

La complexité d’une instruction d’affectation (sans appel de fonction), de lecture ou d’écriture peut
en général se mesurer par θ(1) (indépendant de n).

Séquence
La complexité d’une séquence de n instructions "i" est égale à la somme des complexités de chaque
instruction "i" qui la compose. Coût Séquence(d)=∑i=1...n coût Instruction i(d)

Le choix
La complexité d’une instruction conditionnelle:
Si<condition>alors séquence1 sinon Séquence2 finsi,
est égale à la somme de la complexité d’évaluation de la condition et la plus grande complexité
entre la séquence d’instructions exécutée si la condition est vraie et celle exécutée si la condition est
fausse.
Coût Choix(d)= coût évaluation-condition(d) + Max(coûtséquence1(d), coûtséquence2(d))

Répétition
La complexité d’une boucle est égale à la somme de la complexité de la séquence d’instructions qui
constitue le corps de la boucle et celle de l’évaluation de la condition de sortie.
Coût Boucle(d)= coût évaluation-condition-sortie(d) + coût séquence(d)

Sous-programme
Pour les appels de procédures/fonctions, s’il n’y a pas récursivité, la complexité d’un sous-
programme est égale à la somme des complexités de chacune de ses instructions. Pour les
procédures et fonctions récursives, l’analyse donne en général lieu à la résolution de relations de
récurrences.
Exemples Explicatifs
Déterminons la complexité (trouver une fonction coûtA(d)) de quelques algorithmes classiques afin
d’illustrer les différents cas vus précédemment à travers les exemples suivants.

Exemple 1 :
Calculez le nombre d’actions exécutées par le segment du code suivant:

Pour I←2 jusqu’à n pas 1 faire

somme← somme + I
fin pour

1. Le nombre d’itérations d’une boucle pour est égal à : la valeur finale de l’indice de
parcours, moins sa valeur initiale, plus 1. Dans notre cas, nous avons: n−2+1 = n−1. Le
corps de la boucle a une complexité égale à 1. La condition de sortie (i > n) et évaluée n
fois. Donc, nous avons en tout (n−1)*1+n actions, c-à-d. (2n−1) actions.

2. Nous pouvons voir intuitivement que la valeur de cette expression est proportionnelle à n.
On dit alors qu’elle a un ”ordre de grandeur (ou taux d’augmentation) de n ”. Nous dénotons
ceci en utilisant la notation θ (n). Or, cette expression n’est autre que le temps d’exécution
de cet algorithme en fonction du nombre d’actions et l’entier n (donné), donc coût A(n) ~ θ
(n).

Exemple 2 :
Reprenons la même question pour l’algorithme suivant:
Algorithme moyenne_de_n_nombre

© Belala Faiza Page 5 sur 10

Algorithmique et Structures de 2020-2021 – Semestre 3 Université Constantine 2
Données

Déclaration
n, somme, i, nombre : entier /* N doit être évidement ≠ 0 */
Moyenne : réel
Début
1. Lire(n )
2. somme ← 0
3. i← 1
4. Tant que i <= n faire
5. lire( nombre)
6. somme← somme + nombre
7. i ← i+1
fin tanque
8. moyenne← somme/n
fin
Chacune des actions 1, 2, et 3 sera exécutée une seule fois.
Chacune des actions 5, 6 et 7 sera exécutée n fois.
L’action 4 qui contrôle la boucle sera exécutée n + 1 fois (une exécution supplémentaire est exigée
pour sortir de la boucle),
Et l’action 8 sera exécutée une seule fois. Cela est résumé ci-dessous:

Actions Nombre de fois Temps d'exécution (ordre

de grandeur)
1 1 θ (1).
2 1 θ (1).
3 1 θ (1).
4 n+1 (n+1)θ (1).
5 n nθ (1).
6 n nθ (1).
7 n nθ (1).
8 1 θ (1).

Donc, le temps d’exécution pour cet algorithme sera :

coûtA(n) = [1+1+1+(n+1)+n+n+n+1] θ (1) = (4n + 5) θ (1) ~ θ (n).

Exemple 3:
Soit la boucle intérieure d’un algorithme de tri (dit: "tri par sélection"). Trouvez le nombre d’actions
exécutées et la complexité de cet algorithme?
Algorithme TRI
1. Pour i←1 jusqu’à m-1 faire
2. min_pos ← i;
3. min ← t[min_pos];
4. pour j← i+1 jusqu’à m faire
5. si (t[j] < min) alors
6. min_pos ← j
7. min ← t[min_pos]
Finsi
Finpour
8. t[min_pos] ← t[i];
9. t[i] ← min
Finpour

1. L’action 1 est exécutée m fois (m − 1 + 1);

2. Les actions 2, 3, 8, 9 (chacune des actions a une complexité de l’ordre de θ(1)) sont
exécutées (m − 1) fois, une fois sur chaque itération de la boucle externe.
3. A la première itération ( i = 1):
 l’action 4 est exécutée m fois;
 l’action 5 est exécutée m − 1 fois,

© Belala Faiza Page 6 sur 10

Algorithmique et Structures de 2020-2021 – Semestre 3 Université Constantine 2
Données

 et en supposant le pire cas où les éléments de la collection sont dans un ordre

descendant, les actions 6 et 7 (chacune en θ(1) ) sont exécutées ( m−1) fois.
4. A la deuxième itération ( i = 2),
 l’action 4 est exécutée m − 1 fois
 et les actions 5, 6 et7 sont exécutées m-2 fois, etc.,
 Donc, l’action 4 est exécutée (m) + (m − 1) + ... + 2 = [m(m+1)/2 -1]fois
 et les actions 5, 6, 7 sont exécutés (m − 1)+(m − 2)+...+2+1 = m(m−1)/2 fois.
D’où la complexité maximale est:
coûtTRI(m) = [(m) + 4(m − 1)] θ(1) + [m(m+1)/2 −1] θ(1) + 3[m(m−1)/2] θ(1)
= [m + 4m − 4 + (m2+m)/2 − 1 + (3m2−3m)/2] θ(1)
= (5m − 5 + 2m2 − m) θ(1)
= (2m2 + 4m −5) θ(1)
~ θ (m2)

Exemple 4:
Analysez la complexité des algorithmes suivants en déterminant l’ordre du temps de calcul, pour
chacun d’eux.
Algo. A Algo. B
… …
Début Début
1. i  N 1. i1
2. tant que i >= 0 Faire 2. tant que i <= N faire
3. i  i – 2 3. J  1
fintq 4. tant que J <= N faire
Fin 5. JJ+1
ftq
6. ii+1
ftq
Fin

Algo. C Algo. D
… …
Début Début
1. i  1 1. i  N
2. tant que i <= N faire 2. tant que i >= 1 faire
3. i  i*2 3. i  i / 2
ftq - ftq
Fin Fin
L’ordre de
grandeur en temps
de ces algorithmes est illustré dans le tableau ci-dessous:
Instruction
Algo.A Algo.B Algo.C Algo.D
s
1 (1) (1) (1) (1)
2 (K+1)(1) (N-1+1+1)(1) (K+1)(1) (K+1)(1)
3 K (1) (N-1+1)(1) K(1) K(1)
4 - N (N-1+1+1)(1) - -
5 - (N-1) (N-1)(1) - -
6 - (N-1) (1) - -
CoûtAlgo.A (N)=
total (1+K+1+K)(1) CoûtAlgo.B(N)  CoûtAlgo.C(N)  CoûtAlgo.D(N) 
(N ) (logN) (logN)
2
=(N+4) (1) (N)
Calcul de K pour chacun des morceaux de code précédents (A, C et D) qui demandent une
analyse particulière.

© Belala Faiza Page 7 sur 10

Algorithmique et Structures de 2020-2021 – Semestre 3 Université Constantine 2
Données

Algorithme A
A l’étape 1, I=N
A l’étape 2, I=N-2
A l’étape 3, I=N-2*2
A l’étape K, I= N-2*(K-1)
A la fin I=0  N-2*(K-1) = 0  K= N/2 +1

Algorithme C
A l’étape 1, I=1
A l’étape 2, I=2*1
A l’étape 3, I= 2*2 *1
A l’étape K, I= 2K-1
…
A la fin I=N  2K-1 = N  K= logN +1

Algorithme D
A l’étape 1, I=N
A l’étape 2, I=N/2
A l’étape 3, I= N/2*2
A l’étape K, I= N/2K-1
…
A la fin I=1  2K-1 = N  K= logN +1

Exemple 5:
Analyser le programme suivant :
Procédure foo(donnée/sortie x, n : entiers) ;
Déclaration
i : entier ;
Début
1. Pour i  1 jusqu’à n faire
2. x  x + bar(i, n)
finpour
Fin
Fonction bar(données x, n : entiers) : entier
Déclaration
i : entier ;
Début
3. Pour i =1 jusqu ’à n faire
4. xx+i
finpour
5. retourner(x)
Fin
Algorithme principal
Déclaration
un, n : entiers
Début
6. lire(n)
7. un  0 ;
8. foo(un, n) ;
9. écrire(bar(n, n))
Fin

1- Nous commençons par analyser la fonction bar qui ne fait aucun appel à d’autres sous-
programmes.
La boucle pour ajoute à x la somme des entiers de 1 à n. Donc, la fonction bar(x, n) calcule
l’expression : x+n( n+1)/2. Le temps d’exécution est analysé comme suit :
 Les actions 3 et 4 sont exécutées respectivement n+1 et n fois.
 L’action 5 est exécutée une seule fois.

© Belala Faiza Page 8 sur 10

Algorithmique et Structures de 2020-2021 – Semestre 3 Université Constantine 2
Données

Par conséquent, le temps d’exécution de la fonction bar est de l’ordre de θ(n) + θ(1) = θ(n).
2- Ensuite, nous analysons la procédure foo :
 L’action 2 a normalement une complexité de l’ordre de θ(1). Mais il y a un appel à la
fonction bar, donc le temps d’exécution de l’action 2 est : θ(1) + θ(n) = θ(n).
 Les lignes 1 et 2 se répètent n fois,
Donc la complexité de la procédure est de l’ordre de (n* θ(n)) ~ θ(n2).
3- Finalement, nous analysons l’algorithme principal.
 La complexité de chacune des actions 6 et 7 est de l’ordre θ(1).
 La complexité de l’appel à foo (à la ligne 8) est de l’ordre de θ(n2).
 La complexité de l’action écrire (de ligne 9) égale (à la complexité de l’opération de
L’écriture + la complexité de l’appel de fonction bar) : θ(1) + θ(n).

Donc, le temps d’exécution total pour l’algorithme principal est : θ(1) + θ(1) + θ(n2) +
θ(n)  θ(n2)

4. Différents types de complexité

Il faut remarquer qu’un algorithme peut avoir des comportements différents suivant les données à
traiter. Imaginons que l’on cherche un nom dans un annuaire téléphonique et que notre algorithme
consiste à lire tous les noms depuis le début jusqu’à ce qu’on trouve le bon.
 Si on a beaucoup de chance, le nom cherché est le premier.
 Si, au contraire, on n’a pas de chance du tout, le nom cherché se trouvera en dernier.
 En moyenne, on trouvera le nom après avoir parcouru environ la moitié des pages de
l’annuaire.
Pour notre recherche dans l’annuaire, si on considère que lire un nom est une opération élémentaire,
on aurait pour un annuaire de n noms:
 Premier cas : θ(1)
 Deuxième cas : θ(n)
 Troisième cas: θ(n/2)

On peut donc distinguer trois types de complexité.

Etant donné le coût d'un algorithme A pour une donnée d de taille n (le nombre d'opérations
élémentaires nécessaires au traitement de la donnée d), coûtA(d), les différentes complexités sont :
1. Complexité dans le pire des cas :
MaxA(n) = max{coûtA(di), di  D}

D est l’ensemble des entrées de taille n, selon leur disposition.

2. Complexité dans le meilleur des cas :

MinA(n) = min{coûtA(di), di  D}

3. Complexité en moyenne :
MoyA(n) = di  D p(di) . coûtA(di)

où p(di) est la probabilité d'avoir en entrée la donnée di parmi toutes les données de taille n.

Si toutes les données sont équiprobables, alors on a,

MoyA(n) = 1/Dn di  D coûtA(di)

© Belala Faiza Page 9 sur 10

Algorithmique et Structures de 2020-2021 – Semestre 3 Université Constantine 2
Données

Exemple 6:
Soit T un tableau de taille n contenant des nombres entiers de 1 à k. Soit a un entier entre 1 et k. La
fonction suivante retourne l'indice i de l'un des éléments du tableau lorsqu'il est égal à a, et 0 sinon.
Fonction Proc(Données n, a : entiers, Donnée T: Tab[n] d'entiers ) : entier
Déclarations
i, mem: entier;
Début
mem  0
Pour i =1 jusqu’à n faire
si T[i]=a alors
mem  i
i  n
finsi;
finpour
Retourner(mem);
Fin

Cas le pire : θ(n) (le tableau ne contient pas l'élément a)

Cas le meilleur : θ(1) (le premier élément du tableau est a)
Complexité moyenne : Si les nombres entiers de 1 à k apparaissent de manière équiprobable, on
peut montrer que le coût moyen de l'algorithme est (1-q/2).n + q/2, sachant que q=p [aT].
Si q=1/2 alors MoyA(n)=(n+1)/2 et,
Si q=1/2 alors MoyA(n)=(3n+1)/4

De ce fait, les cas où l'on peut explicitement calculer la complexité en moyenne sont rares. Cette
étude est un domaine à part entière de l'algorithmique que nous n’aborderons pas ici. Toutefois, il
est indispensable, après avoir écrit un algorithme, de calculer sa complexité dans le pire des cas et
dans le meilleur des cas.

© Belala Faiza Page 10 sur 10