Université Mohammed VI Polytechnique

Rappel sur la complexité

Module : Structures de Données

M’hammed El Kahoui

October 23, 2020

Plan

1 Un peu de terminologie

2 Notion de complexité
Taille des données
Opérations élémentaires
Complexité temporelle
Complexité en espace
Le big O

3 Quelques classes de complexité temporelle

2 of 23

M’hammed El Kahoui - Rappel sur la complexité

Algorithmes

• Un algorithme est tout simplement une manière de décrire dans ses

moindres détails comment procéder pour trouver une solution à un
problème donné.

3 of 23

M’hammed El Kahoui - Rappel sur la complexité

Algorithmes

• Un algorithme est tout simplement une manière de décrire dans ses

moindres détails comment procéder pour trouver une solution à un
problème donné.

Definition
Un algorithme est une procédure de calcul bien définie qui prend en entrée
un ensemble de valeurs et qui délivre en sortie un autre ensemble de valeurs.

3 of 23

M’hammed El Kahoui - Rappel sur la complexité

Example

Algorithm 1 Moyenne d’un tableau de réels

Input : Un tableau T de N nombres réels.

Output : Moyenne du tableau T .
Déclaration des variables :
Variable M qui représente la moyenne de T
Variable i pour parcourir le tableau T
Initialisation des variables:
M = 0;
Instructions :
for i = 0 to N − 1 do
M = M + T [i]
end for
M
M=
N
return M

4 of 23

M’hammed El Kahoui - Rappel sur la complexité

Un algorithme est composé de plusieurs parties principales.

5 of 23

M’hammed El Kahoui - Rappel sur la complexité

Un algorithme est composé de plusieurs parties principales.
1. Les données qui représentent l’entrée de l’algorithme.
2. Les résultats qui représentent la sortie de l’algorithme.
3. Le corps de l’algorithme qui est composé entre autres des parties
suivantes.

5 of 23

M’hammed El Kahoui - Rappel sur la complexité

Un algorithme est composé de plusieurs parties principales.
1. Les données qui représentent l’entrée de l’algorithme.
2. Les résultats qui représentent la sortie de l’algorithme.
3. Le corps de l’algorithme qui est composé entre autres des parties
suivantes.
◦ Déclaration des variables qui vont être manipulées par l’algorithme.
◦ Initilisation des variables qui vont être manipulées par l’algorithme.
◦ Les instructions qui permettent d’aboutir au résultat.

5 of 23

M’hammed El Kahoui - Rappel sur la complexité

Un algorithme est composé de plusieurs parties principales.
1. Les données qui représentent l’entrée de l’algorithme.
2. Les résultats qui représentent la sortie de l’algorithme.
3. Le corps de l’algorithme qui est composé entre autres des parties
suivantes.
◦ Déclaration des variables qui vont être manipulées par l’algorithme.
◦ Initilisation des variables qui vont être manipulées par l’algorithme.
◦ Les instructions qui permettent d’aboutir au résultat.

Definition
Une valeur particulière de l’ensemble des valeurs données en entrée à un
algorithme est appelée instance du problème que l’algorithme résoud.

5 of 23

M’hammed El Kahoui - Rappel sur la complexité

Un algorithme est composé de plusieurs parties principales.
1. Les données qui représentent l’entrée de l’algorithme.
2. Les résultats qui représentent la sortie de l’algorithme.
3. Le corps de l’algorithme qui est composé entre autres des parties
suivantes.
◦ Déclaration des variables qui vont être manipulées par l’algorithme.
◦ Initilisation des variables qui vont être manipulées par l’algorithme.
◦ Les instructions qui permettent d’aboutir au résultat.

Definition
Une valeur particulière de l’ensemble des valeurs données en entrée à un
algorithme est appelée instance du problème que l’algorithme résoud.

Par exemple, T = [1, 3, 2, 4] est une instance du problème de calcul de la

moyenne d’un tableau.

5 of 23

M’hammed El Kahoui - Rappel sur la complexité

Definition
Un algorithme qui résoud un problème donné est dit correct si pour toute
instance du problème l’algorithme se termine et produit une sortie correcte.

Example
• Dans l’algorithme 1, si on enlève l’instruction M = 0 l’algorithme ne
retourne plus la moyenne du tableau.

6 of 23

M’hammed El Kahoui - Rappel sur la complexité

Definition
Un algorithme qui résoud un problème donné est dit correct si pour toute
instance du problème l’algorithme se termine et produit une sortie correcte.

Example
• Dans l’algorithme 1, si on enlève l’instruction M = 0 l’algorithme ne
retourne plus la moyenne du tableau.
• En fait, lorsqu’on déclare la variable M on ne sait pas quelle valeur
initiale elle a.
• Si cette valeur est non nulle alors le résultat final n’est pas la moyenne
des valeurs du tableau donné.

6 of 23

M’hammed El Kahoui - Rappel sur la complexité

Example
Voici un exemple d’algorithme qui ne se termine pas.

Algorithm 2 Algorithme qui ne se termine pas

Input : Pas d’entrée.

Output : Pas de sortie.
a+b
a = 1, b = 2, c =
2
while c 2 6= 2 do

if c 2 > 2 then
b=c
else
a=c
end if
a+b
c=
2
end while
7 of 23

M’hammed El Kahoui - Rappel sur la complexité

Notion de complexité

• Un problème donné a en général plusieurs solutions algorithmiques.

• Il est donc important d’avoir un outil objectif qui permet de comparer
ces différentes solutions et d’en choisir la plus performante.

8 of 23

M’hammed El Kahoui - Rappel sur la complexité

Notion de complexité

• Un problème donné a en général plusieurs solutions algorithmiques.

• Il est donc important d’avoir un outil objectif qui permet de comparer
ces différentes solutions et d’en choisir la plus performante.
• Une manière naturelle de mesurer la performance d’un algorithme est
d’estimer le temps de son exécution.
• Cette estimation va bien sûr dépendre de plusieurs facteurs :

8 of 23

M’hammed El Kahoui - Rappel sur la complexité

Notion de complexité

• Un problème donné a en général plusieurs solutions algorithmiques.

• Il est donc important d’avoir un outil objectif qui permet de comparer
ces différentes solutions et d’en choisir la plus performante.
• Une manière naturelle de mesurer la performance d’un algorithme est
d’estimer le temps de son exécution.
• Cette estimation va bien sûr dépendre de plusieurs facteurs :
◦ La performance de l’algorithme.
◦ La taille des données.
◦ La nature et la rapidité des instructions du langage choisi pour
implémenter l’algorithme.
◦ La qualité de la programmation.

8 of 23

M’hammed El Kahoui - Rappel sur la complexité

• On ne cherche pas à mesurer le temps de calcul par rapport à toutes ces
variables.
• Notre mesure ne doit dépendre ni de l’ordinateur, ni du langage utilisé,
ni du programmeur, ni de l’implémentation.
• Pour ceci on utilise le modèle RAM (Random Access Machine) :

9 of 23

M’hammed El Kahoui - Rappel sur la complexité

• On ne cherche pas à mesurer le temps de calcul par rapport à toutes ces
variables.
• Notre mesure ne doit dépendre ni de l’ordinateur, ni du langage utilisé,
ni du programmeur, ni de l’implémentation.
• Pour ceci on utilise le modèle RAM (Random Access Machine) :
◦ Ordinateur idéalisé.
◦ Mémoire infinie.
◦ Accès à la mémoire en temps constant.
◦ Processeur unique (pas d’opérations simultanées).

9 of 23

M’hammed El Kahoui - Rappel sur la complexité

Plan

1 Un peu de terminologie

2 Notion de complexité
Taille des données
Opérations élémentaires
Complexité temporelle
Complexité en espace
Le big O

3 Quelques classes de complexité temporelle

10 of 23

M’hammed El Kahoui - Rappel sur la complexité

Taille des données
• Il est clair que le temps de calcul d’un algorithme dépend de l’instance
sur laquelle l’algorithme est exécuté.
◦ Par exemple, multiplier deux entiers à 10 chiffres chacun prend beaucoup
plus de temps que multiplier deux entiers à 3 chiffres.

11 of 23

M’hammed El Kahoui - Rappel sur la complexité

Taille des données
• Il est clair que le temps de calcul d’un algorithme dépend de l’instance
sur laquelle l’algorithme est exécuté.
◦ Par exemple, multiplier deux entiers à 10 chiffres chacun prend beaucoup
plus de temps que multiplier deux entiers à 3 chiffres.
• Pour estimer le temps de calcul d’un algorithme il est donc important de
préciser la taille des données qui est en fait un nombre entier.

11 of 23

M’hammed El Kahoui - Rappel sur la complexité

Taille des données
• Il est clair que le temps de calcul d’un algorithme dépend de l’instance
sur laquelle l’algorithme est exécuté.
◦ Par exemple, multiplier deux entiers à 10 chiffres chacun prend beaucoup
plus de temps que multiplier deux entiers à 3 chiffres.
• Pour estimer le temps de calcul d’un algorithme il est donc important de
préciser la taille des données qui est en fait un nombre entier.

Table: Exemples de taille de données

Type Taille
Entier Taille d’écriture en binaire
Tableau ou liste Nombre d’éléments × taille maximale des éléments
Polynôme Degré × taille maximale des coefficients
Matrice m × n max(m, n)×taille maximale des éléments
Chaines de caractères Nombre de lettres

11 of 23

M’hammed El Kahoui - Rappel sur la complexité

Plan

1 Un peu de terminologie

2 Notion de complexité
Taille des données
Opérations élémentaires
Complexité temporelle
Complexité en espace
Le big O

3 Quelques classes de complexité temporelle

12 of 23

M’hammed El Kahoui - Rappel sur la complexité

Opérations élémentaires

• Par exemple, la multiplication des entiers ne peut pas être considérée

comme élémentaire.
◦ En effet, le temps de son exécution dépend de l’ordre de grandeur des
entiers qu’on multiplie.
• Il est donc important de préciser ce qu’on peut considérer comme
opérations élementaires.
• Les seules opérations qu’on considérera comme élémentaires sont :
◦ Lecture dans une case mémoire.
◦ Écriture dans une case mémoire.

13 of 23

M’hammed El Kahoui - Rappel sur la complexité

Plan

1 Un peu de terminologie

2 Notion de complexité
Taille des données
Opérations élémentaires
Complexité temporelle
Complexité en espace
Le big O

3 Quelques classes de complexité temporelle

14 of 23

M’hammed El Kahoui - Rappel sur la complexité

Complexité temporelle
La complexité temporelle d’un algorithme est une mesure du temps de
calcul utilisé par cet algorithme, exprimée en fonction de la taille de l’entrée
de l’algorithme.

15 of 23

M’hammed El Kahoui - Rappel sur la complexité

Complexité temporelle
La complexité temporelle d’un algorithme est une mesure du temps de
calcul utilisé par cet algorithme, exprimée en fonction de la taille de l’entrée
de l’algorithme.
Soient A un algorithme et n un entier et soit Dn l’ensemble des entrées de
A de taille n. Pour chaque d ∈ Dn on note CA (d) le nombre d’opérations
élémentaires effectuées par l’algorithme A sur l’entrée d.

15 of 23

M’hammed El Kahoui - Rappel sur la complexité

Complexité temporelle
La complexité temporelle d’un algorithme est une mesure du temps de
calcul utilisé par cet algorithme, exprimée en fonction de la taille de l’entrée
de l’algorithme.
Soient A un algorithme et n un entier et soit Dn l’ensemble des entrées de
A de taille n. Pour chaque d ∈ Dn on note CA (d) le nombre d’opérations
élémentaires effectuées par l’algorithme A sur l’entrée d.

Definition
La complexité temporelle dans le pire des cas, ou simplement complexité
temporelle, de l’algorithme A est la fonction TA : N? −→ R?+ définie pour
tout n ∈ N? par
TA (n) = max CA (d).
d∈Dn

15 of 23

M’hammed El Kahoui - Rappel sur la complexité

Plan

1 Un peu de terminologie

2 Notion de complexité
Taille des données
Opérations élémentaires
Complexité temporelle
Complexité en espace
Le big O

3 Quelques classes de complexité temporelle

16 of 23

M’hammed El Kahoui - Rappel sur la complexité

Complexité en espace
La complexité en espace est une mesure de l’espace mémoire utilisé par un
algorithme, exprimée comme fonction de la taille de l’entrée.

17 of 23

M’hammed El Kahoui - Rappel sur la complexité

Complexité en espace
La complexité en espace est une mesure de l’espace mémoire utilisé par un
algorithme, exprimée comme fonction de la taille de l’entrée.
Soient A un algorithme et n un entier et soit Dn l’ensemble des entrées de
A de taille n. Pour chaque d ∈ Dn on note MA (d) la taille de l’espace
mémoire utilisé par l’algorithme A sur l’entrée d.

17 of 23

M’hammed El Kahoui - Rappel sur la complexité

Complexité en espace
La complexité en espace est une mesure de l’espace mémoire utilisé par un
algorithme, exprimée comme fonction de la taille de l’entrée.
Soient A un algorithme et n un entier et soit Dn l’ensemble des entrées de
A de taille n. Pour chaque d ∈ Dn on note MA (d) la taille de l’espace
mémoire utilisé par l’algorithme A sur l’entrée d.

Definition
La complexité en espace dans le pire des cas, ou simplement complexité en
espace, de l’algorithme A est la fonction SA : N? −→ R?+ définie pour tout
n ∈ N? par
SA (n) = max MA (d).
d∈Dn

17 of 23

M’hammed El Kahoui - Rappel sur la complexité

Plan

1 Un peu de terminologie

2 Notion de complexité
Taille des données
Opérations élémentaires
Complexité temporelle
Complexité en espace
Le big O

3 Quelques classes de complexité temporelle

18 of 23

M’hammed El Kahoui - Rappel sur la complexité

Le big O
• Pour mesurer la performance d’un algorithme A on n’a pas besoin de
calculer précisement les fonction TA et SA .
• On a juste besoin de savoir quel genre de comportement elles ont pour
de très grandes valeurs de n.

19 of 23

M’hammed El Kahoui - Rappel sur la complexité

Le big O
• Pour mesurer la performance d’un algorithme A on n’a pas besoin de
calculer précisement les fonction TA et SA .
• On a juste besoin de savoir quel genre de comportement elles ont pour
de très grandes valeurs de n.

Definition
Soient f , g : N −→ R+ . On dit que f est en grand O de g , et on note
f = O(g ), s’il existe une constante c ∈ R+ et n0 ∈ N telles que

∀ n ≥ n0 f (n) ≤ cg (n).

Lorsque f = O(g ) et g = O(f ) on écrit f = Θ(g ).

19 of 23

M’hammed El Kahoui - Rappel sur la complexité

Example
Si f (n) = 3n + 5 alors on a f (n) = Θ(n). De même, si
f (n) = 2n2 + 3n + 2 alors g (n) = Θ(n2 ).

Theorem
Soient f , g , h, k : N −→ R+ des fonctions. Alors on a les propriétés
suivantes.
f (n)
1. Si g ne s’annule pas et lim = c ∈ R? alors f (n) = Θ(g (n)).
n→∞ g (n)

2. Si f (n) = O(g (n)) et g (n) = O(h(n)) alors f (n) = O(h(n)).

3. Si f (n) = O(g (n)) et h(n) = O(k(n)) alors f (n)h(n) = O(g (n)k(n)).
4. Si f (n) = O(h(n)) et g (n) = O(h(n)) alors f (n) + g (n) = O(h(n)).

20 of 23

M’hammed El Kahoui - Rappel sur la complexité

Example
Si f (n) = 3n + 5 alors on a f (n) = Θ(n). De même, si
f (n) = 2n2 + 3n + 2 alors g (n) = Θ(n2 ).

Theorem
Soient f , g , h, k : N −→ R+ des fonctions. Alors on a les propriétés
suivantes.
f (n)
1. Si g ne s’annule pas et lim = c ∈ R? alors f (n) = Θ(g (n)).
n→∞ g (n)

2. Si f (n) = O(g (n)) et g (n) = O(h(n)) alors f (n) = O(h(n)).

3. Si f (n) = O(g (n)) et h(n) = O(k(n)) alors f (n)h(n) = O(g (n)k(n)).
4. Si f (n) = O(h(n)) et g (n) = O(h(n)) alors f (n) + g (n) = O(h(n)).

On a des propriétés analogues si on remplace O par Θ.

20 of 23

M’hammed El Kahoui - Rappel sur la complexité

Quelques classes de complexité temporelle

Table: Quelques classes de complexité temporelle

Complexité Nom courant Description
O(1) Constante Le temps d’exécution ne dépend
pas de la taille des données.
O(ln(n)) Logarithmique Augmentation très faible du temps
d’exécution en fonction de la
taille des données.
O(n) Linéaire Augmentation linéraire du temps
d’exécution en fonction de la
taille des données.
O(n ln(n)) Quasi-linéaire Augmentation presque en O(n)
O(n2 ) Quadratique Quand la taille des données
double le temps est mutliplié par 4.
O(nk ), k fixe Polynomiale Par exemple O(n3 ), O(n4 ).
O(k n ), k > 1 fixe Exponentielle Le temps d’exécution augmente
trop vite en fonction de la
taille des données. 21 of 23

M’hammed El Kahoui - Rappel sur la complexité

 Table: Temps d’exécution en fonction de la complexité temporelle
O(ln(n)) O(n) O(n ln(n)) O(n2 ) O(n3 ) O(2n )
102 7 ns 100 ns 0.7 µs 10 µs 1 ms 4.1013 années
103 10 ns 1 µs 10 µs 1s 1s
104 13 ns 10 µs 133 µs 100 ms 17 s
105 17 ns 100 µs 2 µs 10 s 11, 6 jours

Les temps de calcul dans le tableau ci-dessus sont donnés à titre

d’illustration.

22 of 23

M’hammed El Kahoui - Rappel sur la complexité

Complexité de quelques opérations de base

On donne dans cette table la complexité de certaines opérations de base sur

deux entiers x et y de tailles respectives τ1 et τ2 . On prend τ = max(τ1 , τ2 )
comme taille de la donnée (x, y ).

23 of 23

M’hammed El Kahoui - Rappel sur la complexité

Complexité de quelques opérations de base

On donne dans cette table la complexité de certaines opérations de base sur

deux entiers x et y de tailles respectives τ1 et τ2 . On prend τ = max(τ1 , τ2 )
comme taille de la donnée (x, y ).

Table: Complexité de quelques opérations de base sur les entiers

Opération +, − ∗ = ==, <, >

Temps O(τ ) O(τ 2 ) O(τ ) O(τ )
Espace ≤τ +1 ≤ 2τ τ O(1)

23 of 23

M’hammed El Kahoui - Rappel sur la complexité