Ecole Supérieure en Sciences et Technologies

de l’Informatique et du Numérique

Chapitre V: La Complexité Algorithmique

Algorithmique et Structures de
Données Dynamiques

1re année Ecole Prépa. De l’ESTIN de Bejaia

Année: 2020-2021
 Chapitre V: La Complexité Algorithmique
Introduction
Tout au long de ce module, vous avez appris à développer des
programmes (et des modules sous forme de fonctions et de procédures).
En comparant ces programmes avec les autres programmes proposés par
vos camarades, vous les trouvez souvent différents. Ceci est normal car
un problème donné peut avoir plusieurs solutions, et donc plusieurs
algorithmes implémentant ces solutions.

Vous vous êtes certainement poser la question par rapport à la meilleur

solution parmi celles proposées (meilleure solution ?) et en quoi cette
dernière est meilleur (meilleure en quoi ?)

2
 Chapitre V: La Complexité Algorithmique
Introduction
Deux algorithmes répondant au même besoin et renvoyant les mêmes
résultats peuvent être différents en termes d’espace et/ou de temps. Nous
parlons, par conséquent, de :
— La complexité en temps d’exécution,
— La complexité en espace (mémoire, ou même disque, ou autres
ressources) nécessaire pour que l’algorithme fonctionne.

Nous considérons dans ce cours la complexité en temps d’exécution. En

d’autres termes : à quel point un algorithme est-il rapide ?

3
 Chapitre V: La Complexité Algorithmique
Exemple Introductif 1:
 Problème :
Supposons que l’on vous demande de stocker une séquence
d’entiers dont le nombre est inconnu avant l’exécution du
programme.

 Solution:
Vous optez pour une liste linéaire chainée. Vous pensez donc à
insérer des éléments dans une LLC. Il existe au moins deux façons
de le faire, à savoir :
— Insertion de chaque nouvel élément à la tête de la liste,
— Insértion à la fin de la liste.

4
 Chapitre V: La Complexité Algorithmique
Exemple Introductif 1:
 Comparaison des deux approches :
Essayez de comparez les deux solutions !

A votre avis quelle est la meilleure solution ?

Bien évidement la première solution est plus rapide que la

deuxième.

5
 Chapitre V: La Complexité Algorithmique
Exemple Introductif 1:
 Comparaison des deux approches :
La première alloue de l’espace pour l’élément, y met l’entier en question,
et fait en sorte qu’il soit la nouvelle tête de la LLC.
La deuxième, en revanche, après avoir alloué l’espace et y avoir mis la
valeur, parcoure la liste jusqu’à la fin pour y insérer l’élément
nouvellement créé.
Remarquez bien que le temps pris par le premier algorithme est constant
et ne dépend nullement de la taille de la liste, alors que le second
algorithme prendrait plus de temps (à parcourir la liste) à mesure que la
liste devienne plus longue.

Il ne suffit pas donc d’écrire un algorithme qui fonctionne, mais il est aussi
souvent important qu’il soit efficace.
6
 Chapitre V: La Complexité Algorithmique
Définition
La complexité temporelle d’un algorithme est la mesure du nombre
d’opérations fondamentales effectuées sur un ensemble de données, telles
que les affectations, les tests et les opérations arithmétiques.

La complexité est exprimée comme une fonction de la taille de données

traitées. Ce qui permet de comparer deux algorithmes traitant le même
calcul.

L’étude de la complexité d’un algorithme consiste essentiellement à

évaluer la dépendance entre le temps d’exécution et le volume de
données.

7
 Chapitre V: La Complexité Algorithmique
Exemple introductif 2 :
 Problème :
Rechercher une valeur donnée dans un ensemble de n éléments non
triés.
 Solution:
Examiner chaque élément jusqu’à trouver ce que l’on cherche.

 Complexité :
Dans le meilleur cas, cela prendra une seule comparaison, dans le
pire cas, il faudra effectuer n comparaisons. En moyenne, nous
aurons n/2 comparaisons à effectuer.

8
 Chapitre V: La Complexité Algorithmique
Exemple introductif 2 :
 Complexité :
 Complexité au meilleur cas : C’est les plus petit nombre
d’opérations qu’aura à exécuter l’algorithme sur un ensemble de
données de taille fixe (n).
 Complexité au pire cas : C’est le plus grand nombre d’opérations
qu’aura à exécuter l’algorithme sur un ensemble de données de
taille fixe (n).
 Complexité en moyenne : C’est la moyenne des complexités de
l’algorithme sur l’ensemble de données de taille n.

En général, on considère qu’un algorithme est plus efficace qu’un

autre si sa complexité dans le pire cas a un ordre de grandeur
inférieur.
9
 Chapitre V: La Complexité Algorithmique
Notation de Landau

L’exemple introductif 1 nous a donné une idée de la différence qu’il peut y

avoir entre deux algorithmes censés faire la même chose. Mais comment
traduit-on cette différence de façon formelle ou mathématique ?

Avant de le faire, commençons par une explication intuitive. Lorsque nous

insérons un élément à la tête d’une liste, le temps d’exécution ne dépend pas
de la taille de la liste. Alors que lorsque nous l’insérons à la queue, plus il y a
d’éléments dans la liste plus le programme prendra de temps pour le faire,
et ce de façon linéaire.

10
 Chapitre V: La Complexité Algorithmique
Notation de Landau
Lorsqu’un programme nécessite un temps d’exécution constant et
indépendant de la taille des données (n) à traiter, nous disons que sa
complexité est constante, et est égale à O(1), et c’est prononcé comme suit
: Big-O de 1. La différence en temps d’exécution quand n est incrémenté
est de 0.

Lorsqu’un algorithme nécessite n fois plus de temps qu’il prendrait pour le

faire lorsqu’il n’y a qu’une seule donnée, nous disons que sa complexité est
linéaire et nous la notons par O(n). Si n est incrémenté de 1, le nombre
d’éléments à parcourir est lui aussi incrémenté de 1.

11
 Chapitre V: La Complexité Algorithmique
Notation de Landau
Maintenant supposons que l’on souhaite chercher le maximum d’une
matrice carrée n × n. Il faut donc parcourir chaque ligne de cette matrice,
et pour chacune de ces lignes parcourir chaque colonne aussi.
Nous devons effectuer n × n vérifications pour connaitre ce maximum.
Nous disons dans ce cas que cet algorithme est d’une complexité
quadratique et c’est noté par O(n2). Si n est incrémenté de 1, nous aurons
(n+1)2 de cases à traiter, et pas seulement n + 1.

Supposons que nous recherchons une valeur donnée x dans un arbre

binaire de recherche (BST) qui a n nœuds. Remarquez qu’à chaque
itération nous éliminons une branche de l’arbre de façon récursive. Au
pire donc nous prendrons log(n) itérations et la complexité
logarithmique est notée justement par O(log(n)).

12
 Chapitre V: La Complexité Algorithmique
Notation de Landau Pour plus de détails quant à
l’aspect mathématique de la
 Formellement notation de Landau, revoir le
cours d’analyse mathématique.
Supposons que le temps d’exécution d’un algorithme donné soit défini par une
fonction T(n) où n est le nombre de données.
Nous disons que: T(n) est O(f(n)) si et seulement s’il existe deux constantes c
∈ ℝ et n0∈ℕ pour lesquelles T(n) ≤ c*f(n) et ce pour tout n ≥ n0.
La fonction f(n) est une borne supérieure pour T(n).
C’est à dire, si l’on comparait le taux de croissance de T(n) nous dirons qu’ils
est inférieur à celui de f(n).
 Comportement asymptotique
Le but de cette analyse est de comprendre le comportement dit
asymptotique de l’algorithme. C’est à dire, de connaitre son efficacité
lorsque n est très grand.
Si un algorithme donné est d’une complexité égale à O(f(n)), alors on
s’attend à ce que son temps d’exécution ne croisse pas plus que f(n).
13
 Chapitre V: La Complexité Algorithmique
Notation de Landau
 Comportement asymptotique

Quand nous calculons la complexité d’un algorithme, nous ne

calculons généralement pas sa complexité exacte, mais son ordre de
grandeur. Pour ce faire, nous avons besoin de notations
asymptotiques.

𝐓 = 𝐎 𝐟 ⇔ ∃ 𝒏𝟎 , ∃ 𝒄 ≥ 𝟎, ∀ 𝒏 ≥ 𝒏𝟎 , 𝑻 𝒏 ≤ 𝒄 ∗ 𝒇 𝒏

On dit que T est O(f) (T est asymptotiquement dominée par f)

14
 Chapitre V: La Complexité Algorithmique
 Quelques caractéristiques du Big-O

— La somme : Soient T1 et T2 les temps d’exécution de deux parties

consécutives P1 et P2 d’un programme donné.
Si T1(n) est O(f(n)) et T2(n) est O(g(n)), alors T1 (n) + T2 (n) est
O(max(f(n), g(n))).
En d’autres termes : O(f(n)) + g(n)) = O(max(f(n), g(n))).

— Multiplication par une constante (O(kf(n))) = O(f(n)).

— Produit : O(f(n) × g(n)) = O(f(n)) × O(g(n)).

16
 Chapitre V: La Complexité Algorithmique
 Autres notations

En plus du Big-O, il existe d’autres notations qui décrivent d’autres

bornes, notamment :

Big-Omega : T(n) est Ω(f(n)) si et seulement s’il existe c ∈ ℝ et n0∈ℕ

tels que: T(n) ≥ f(n) pour tout n ≥ n0.

Theta : T(n) est θ(f(n)) si T(n) est O(f(n)) et T(n) est Ω(f(n)).

Little- ο : T(n) est ο(f(n)) si T(n) est O(f(n)) et T(n) n’est pas θ(f(n)).

17
 Chapitre V: La Complexité Algorithmique
Quelques complexités usuelles

Dans l’analyse des programmes, nous retrouvons souvent ces

quelques complexités classées de la plus faible à la plus forte.

 O(log(n)) : Logarithmique
 O(n) : Linéaire
 O(n2) : Quadratique
 O(nk) : Polynomiale avec k>2
 O(nn), O(ak), O(n!) : Exponentielle

18
 Chapitre V: La Complexité Algorithmique
Règles de calcul
Pour calculer la complexité d’un algorithme, nous avons quelques règles
simples à suivre :
1. Toute opération élémentaire est d’une complexité constante O(1), car son
temps d’exécution est constant et ne dépend pas de la taille des données.
2. La complexité d’une séquence de deux blocs d’instructions P1 et P2 est
égale à la complexité du plus grand d’entre eux.
3. La complexité d’une instruction conditionnelle (si/sinon) est égale à la
complexité du bloc le plus complexe. C’est un peu comme si l’on
envisageait le cas où le bloc ayant la plus grande complexité serait exécuté.
4. La complexité d’une boucle est égale à la somme des complexités de
toutes les itérations du bloc. Si, par exemple, nous avons une boucle
“pour’’ ne contenant que des instruction élémentaires, sa complexité serait
égale à la somme, et si cette boucle itère sur les données, elle serait donc de
O(n).
19
 Chapitre V: La Complexité Algorithmique
Quelques exemples
Nous présentons quelques exemples d’illustration. En les analysant, et en
essayant d’appliquer les règles ci-dessus, vous arriverez à calculer la
complexité d’autres algorithmes par vous-mêmes.

 Recherche dans un tableau

La recherche d’un élément dans un tableau non trié est d’une complexité
égale à O(n), car nous devons itérer n fois au pire pour trouver (ou pas)
la valeur recherchée, et le nombre d’itérations croitra avec le nombre
d’éléments dans le tableau.

8 11 2 6 -3 0 10 17 23 4

Si la par exemple la valeur recherchée est v=12. Dans ce cas, on va

parcourir toutes les cases pour savoir à la fin que la valeur n’existe pas
dans le tableau.
20
 Chapitre V: La Complexité Algorithmique
 Recherche dans un tableau trié
Si le tableau est trié : nous adoptons une recherche par dichotomie, donc
nous éliminons n/2 à chaque fois.
La complexité d’un tel algorithme est beaucoup plus faible que la
précédente car elle est égale à O(log(n)).
À titre d’exemple, prenez un tableau de 8 éléments. Nous nous
positionnons au milieu, si la valeur recherchée est inférieure à celle du
milieu, nous limitons notre recherche au premier 4 éléments du tableau
(sinon aux 4 derniers).
Nous refaisons cette opération avec ce sous-tableau de 4 éléments, et ainsi
de suite. En d’autres termes, au bout d’au plus 3 itérations nous avons
notre réponse. (8 = 23 donc 3 = log(8))

-6 2 5 11 19 23 30 45
21
 Chapitre V: La Complexité Algorithmique
 Produit matriciel
Le produit de deux matrices A et B : Nous multiplions et additionnons les
lignes de A par les colonnes de B. Nous avons trois boucles imbriquées et
qui dépendent toutes les deux de la taille des données. La complexité est
donc égale à O(n) × O(n) × O(n) = O(n3).

Fonction produit ( A, B : Mat) : Mat

Var N, P, i, j, k :Entier C: Mat
Début
Pour i allant de 1 jusqu’à N Faire
Pour j allant de 1 jusqu’à N Faire
P← 0
Pour k allant de 1 jusqu’à N Faire
P ← P + A[i, k] * B[k, j]
FinPour
C[i, j] ← P
FinPour
FinPour
Retourner C
Fin 22
 Chapitre V: La Complexité Algorithmique
 Combinaisons
Supposez que vous avez un clavier avec des chiffres de 0 à 9.
L’algorithme qui affiche les combinaisons possibles de n
chiffres (pas forcément distincts) devrait effectuer 10n itérations.
Sa complexité est de O(10n).

Maintenant considérez un ensemble de caractères (26 lettres,

10 chiffres, et plein de symboles). Donc, plus un mot de passe
contient de caractères plus il est difficile à deviner par la force
brute (en essayant toutes les combinaisons possibles).

23
 Chapitre V: La Complexité Algorithmique
 Exemple 1:
Ecrire l’algorithme qui calcule la somme suivante, ensuite essayer
de calculer sa complexité. S = 1+2 + … + n
 Exercice 1: Solution
Algorithme Calcul
Var S, n, i :Entier
Début
Ecrire(‘ Donner la valeur de n’)
Lire(n)
S← 0
Pour i allant de 1 jusqu’à n faire
S← S+i
FinPour
Ecrire(‘ La somme est :’, S)
Fin.

24
 Chapitre V: La Complexité Algorithmique
 Exemple 1: Solution
Calculer de la complexité
Instruction Nombre d’opérations Nombre d’exécution
Ecrire (‘Donner n’) 1 1
Lire (n) 1 1
S← 0 1 1
i← 1 1 1
i≤ n 1 n+1
S← S+i 2 n
i← i+1 2 n
Ecrire (S) 1 1

C(n)=1+1+1+1+(n+1)+2n+2n+1 = 5n+6
Sa complexité est O(n): C’est une complexité linéaire

25
 Chapitre V: La Complexité Algorithmique
 Exemple 2:

Ecrire l’algorithme qui permet de chercher un élément dans un

tableau non trié, ensuite essayer de calculer sa complexité.

26
 Chapitre V: La Complexité Algorithmique
 Exemple 2 : Solution
Algorithme Recherche
Var T: Tableau[1..50] d’Entier
val, n, i :Entier bool: Booléen
Début
Lire (val)
Lire(n)
Pour i allant de 1 jusqu’à n faire
Lire(T[i])
FinPour
i ← 1, bool ← faux
Tant que (i ≤ n) et (bool = faux) faire
Si (T[i] ≠ val ) Alors
i← i+1 …
Sinon Si bool= vrai Alors
bool ← vrai Ecrire (‘La valeur existe dans le tableau’)
FinSi Sinon
FinTantque Ecrire (‘La valeur n’’existe pas dans le tableau’)
…. FinSi
Fin.
27
 Chapitre V: La Complexité Algorithmique
Instruction Nombre d’opérations Nombre d’exécution Meilleur cas Pire cas
Lire (val) 1 1
Lire (n) 1 1
i← 1 1 1
i≤ n 1 n+1
Lire (T[i]) 1 n
i← i+1 2 n
i← 1 1 1
bool ← faux 1 1
(i≤n) et (bool= faux) 3 2 n+1
T[i] ≠ val 1 1 n
i← i+1 2 0 n
bool ← vrai 1 1 1
bool = vrai 1 1 0
Ecrire (‘ elle existe’) 1 1 0
Ecrire (‘n’existe pas’) 1 0 128
 Chapitre V: La Complexité Algorithmique
 Exemple 2:
Meilleur cas: c’est le cas où la valeur se trouve dans la première case du
tableau: val=T[1]
CMC(n)= 1+1+1+(n+1)+n+2n+1+1+6+1+0+1+1+1+0
= 4n +16
CMC(n)= 4n +16, c’est une complexité linéaire

Pire cas: c’est le cas où la valeur n’existe pas dans le tableau:

CPC(n)= 1+1+1+(n+1)+n+2n+1+1+3(n+1)+n+2n+1+0+0+1
= 10n +11
CPC(n)= 10n +11, c’est une complexité linéaire

29
 Chapitre V: La Complexité Algorithmique
 Exemple 3:
Ecrire une procédure qui permet d’afficher le produit des éléments de deux
tableaux.

Procédure Produit (T1, T2: Tableau[1..50] d’Entier)

Var i, j :Entier
Début
Pour i allant de 1 jusqu’à n faire
Pour j allant de 1 jusqu’à n faire
Ecrire(T1[i]*T2[j])
FinPour
FinPour
Fin
La première boucle sera exécutée n fois et la deuxième n fois, les deux
seront exécutées n*n fois donc sa complexité est O(n2) , c.-à-d. c’est une
complexité quadratique.
30
 Chapitre V: La Complexité Algorithmique
 Exemple 4:
Ecrire une Fonction récursive qui permet de calculer Xn.
Fonction Puissance (X, n: Entier): Entier
Début
Si n=0 Alors
Retourner 1
Sinon
Retourner X * Puissance (X, n-1)
FinSi
Fin

Pour calculer par exemple X3, Cette fonction va donner le résultat

comme suit:
X3 = X* X2 = X *(X * X1 ) = X * X* (X * X0 ) = X * X* (X * 1)
Pour calculer X3 , on a trouvé 3 multiplications. En effet pour calculer
Xn, on aura n multiplications; donc sa complexité est O(n) , c.-à-d. c’est
une complexité linéaire. 31
 Chapitre V: La Complexité Algorithmique
 Exemple 5:
Ecrire une Fonction récursive qui permet de calculer Factorielle d’un
entier.
Fonction Fact (N: Entier): Entier
Début
Si n=0 Alors
Retourner 1
Sinon
Retourner N * Fact (N-1)
FinSi
Fin
c1 test, c2 multiplication.
T(0)= c1
T(n)= c1 + c2 +T(n-1)
⇒ T(n) = n c2 + (n + 1) c1
Soit C = 2max{c1, c2}
T(n) ≤ Cn + c1 = O(n) Complexité en O(n). 32