Complexité des algorithmes

Module INF301 - IMT Nord Europe

IMT Nord-Europe
[Link]@[Link]

17 août 2023

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 1 / 39
 Retour sur le cours/TP de la semaine dernière

Des questions ?

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 2 / 39
 Motivations

Des ressources limitées :

Calcul : temps processeur (nombre d’instructions/seconde limité)
Espace mémoire : RAM, disque dur
En fonction du matériel : la bande passante, la batterie, etc.

L’espérance de vie d’un homme est limitée !

En 2019 : 79.8 ans pour les hommes, 85.7 ans pour les femmes.

Besoin de
comparer les algorithmes
identifier les cas favorables, moyens, défavorables
avoir un ordre de grandeur

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 3 / 39
 La complexité algorithmique

Définition :
L’analyse de la complexité d’un algorithme consiste en l’étude formelle de
la quantité de ressources nécessaire à l’exécution de cet algorithme.

On peut analyser la complexité en temps/temporelle (temps CPU) ou en

espace mémoire/spatiale (mémoire) car ces deux ressources sont limitées !

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 4 / 39
 La complexité algorithmique

La complexité d’un algorithme s’exprime en fonction de la taille des

données à traiter (souvent noté n).

En générale, on ne s’intéresse pas à la complexité exacte (fastidieux et

inutile de tout compter), mais à son ordre de grandeur !
→Choix d’une seule instruction à compter.

Trois étapes à suivre :

1 Définir l’unité de mesure → une instruction élémentaire
2 Calculer le nombre d’instructions élémentaires T(n) en fonction de la
taille des données n
3 Calculer une borne supérieure f(n) de T(n)

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 5 / 39
 Les opérations/instructions élémentaires

Une instruction élémentaire est une (unique !) instruction choisie dans

l’algorithme et que l’on va compter. Ce peut être :
une opération arithmétique (-,+,*)
un test booléen, comparaison
un appel de fonction
une ligne de pseudo-code, etc.

NB : Comme on s’intéresse à approcher au maximum la complexité de

l’algorithme, on choisira l’opération élémentaire la plus exécutée dans
l’algorithme (dans une boucle, dans le cas récursif d’une fonction récursive,
etc.).

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 6 / 39
 1ère approche : décompte des opérations
Tester l’existence d’un élément dans un tableau
Algorithme 1 : Teste l’existence d’un élément dans un tableau.
1 fonction existe(e : Élément, t : Tableau) : Booléen
entrée : e : élément recherché
t : tableau dans lequel on recherche l’élément
sortie : existe : vrai si l’élément existe dans le tableau t, faux sinon
2 existe ← Faux
3 pour i de 0 à (longueur(t) - 1) faire
4 si t[i] = e alors
5 existe ← Vrai
6 fin
7 fin
8 retourner existe
9 fin
Opération élémentaire : comparaison logique de la ligne 4
T(n) = n comparaisons (avec n la taille du tableau)
Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 7 / 39
 1ère approche : décompte des opérations
Recherche des elts distincts dans un tableau - version naı̈ve
Algorithme 2 : Liste les éléments distincts d’un tableau.
1 fonction uniques(t : Tableau) : Tableau
entrée : t : tableau dont on cherche les éléments distincts
sortie : distincts : tableau contenant les éléments distincts de t
2 nb distincts ← 0
3 pour i de 0 à (longueur(t) - 1) faire
4 si non existe(t[i], distincts) alors
5 distincts[nb distincts] ← t[i]
6 nb distincts ← nb distincts + 1
7 fin
8 fin
9 retourner distincts
10 fin
Opération élémentaire : appel de la fonction existe de la ligne 4
T(n) = n fois existe sur un tableau de taille k̂ (pour simplifier)
Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 8 / 39
 1ère approche : décompte des opérations
Algorithme 3 : Teste l’existence d’une valeur dans un tableau.
1 fonction existe sentinelle(e : Élément, t : Tableau) : Booléen
entrée : e : élément recherché
t : tableau dans lequel on recherche l’élément e
sortie : elt existe : vrai si l’élément e existe dans t, faux sinon
2 elt existe ← Faux, i ← 0
3 tant que i < (longueur(t)) et non elt existe faire
4 si t[i] = e alors
5 elt existe ← Vrai
6 fin
7 i←i+1
8 fin
9 retourner elt existe
10 fin
Opération élémentaire : comparaison logique de la ligne 4
Meilleur cas → T(n) = 1, cas moyen → T(n) = n/2, pire cas → T(n) = n
Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 9 / 39
 1ère approche : décompte des opérations
Algorithme 4 : Liste les éléments distincts d’un tableau par tri.
1 fonction uniques rapide(t : Tableau) : Tableau
entrée : t : tableau dont on cherche les éléments distincts
sortie : distincts : tableau contenant les éléments distincts de t
2 nb distincts ← 0
3 trier(t) // De l’ordre de [Link] (n) pour les meilleurs algos
4 distincts[0] ← t[0]
5 pour i de 1 à (longueur(t) - 1) faire
6 si t[i] ̸= t[i-1] alors
7 distincts[nb distincts] ← t[i]
8 nb distincts ← nb distincts + 1
9 fin
10 fin
11 retourner distincts
12 fin
T(n) = Ttrier (n)+Tboucle (n)= [Link] (n) + (n − 1) comparaisons
Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 10 / 39
 1ère approche : décompte des opérations

Les petits n ne sont pas un problème : les différences entre algos se font
voir pour de grands n.

Comment comparer la croissance des fonctions ? → étude asymptotique

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 11 / 39
 2ème approche : analyse asymptotique

Problème : Comment comparer ces grandeurs ?

La notation de Landau :

On note f (n) la fonction étudiée et g (n) la fonction à laquelle on se

compare, quand n croı̂t. Fonctions définies sur N.

f (n) = O(g (n)) → Ordre de grandeur maximal de complexité (Borne

supérieure) :
O(g (n)) = {f (n)|∃c ∈ R, c > 0, n0 ∈ N, ∀n > n0 , 0 ≤ f (n) ≤ c.g (n)}

O(g(n))→ l’ensemble des fonctions qui croissent au plus aussi vite que g.

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 12 / 39
 2ème approche : analyse asymptotique

On note f (n) la fonction étudiée et g (n) la fonction à laquelle on se

compare, quand n croı̂t. Fonctions définies sur N.

f (n) = Ω(g (n)) → Ordre minimal de complexité (Borne inférieure) :

Ω(g (n)) = {f (n)|∃c ∈ R, c > 0, n0 ∈ N, ∀n > n0 , 0 ≤ c.g (n) ≤ f (n)

Ω(g(n))→ l’ensemble des fonctions qui croissent au moins aussi vite que g.

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 13 / 39
 2ème approche : analyse asymptotique

On note f (n) la fonction étudiée et g (n) la fonction à laquelle on se

compare, quand n croı̂t. Fonctions définies sur N.
f (n) = Θ(g (n)) → Ordre de grandeur exact de complexité
(Encadrement) :
Θ(g (n)) = {f (n)|∃c1 ∈ R, c1 > 0, c2 ∈ R, c2 > 0, n0 ∈ N, ∀n > n0 , 0 ≤
c1 .g (n) ≤ f (n) ≤ c2 .g (n)}

Théorème : f (n) = Θ(g (n)) ⇐⇒ f (n) = O(g (n)) et f (n) = Ω(g (n))

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 14 / 39
 2ème approche : analyse asymptotique

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 15 / 39
 Abus de notation
Notation correcte : f (n) ∈ Θ(g (n))
Notation employée : f (n) = Θ(g (n)) → permet de mettre les
notations dans des équations

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 16 / 39
 Classes de complexité

Classes courantes de complexité :

constante : Θ(1)
linéaire : Θ(n)
logarithmique : Θ(log2 (n))
log-linéaire (“linearithmic”) : Θ(n. log2 (n))
quadratique : Θ(n2 )
cubique : Θ(n3 )
polynomiale : Θ(nc ), c ∈ R+∗
exponentielle : Θ(c n ), c > 1
factorielle : Θ(n!)

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 17 / 39
 Ordre de grandeur des temps d’exécution de quelques
classes de complexité
→ une instruction en 10−8 secondes.
La Table ci-dessous donne les temps d’exécution estimés pour des
algorithmes des principales classes de complexité, en ignorant les facteurs
constants (qui multiplieraient en pratique les temps d’exécution par une
constante).

n Θ(1) Θ(log2 (n)) Θ(n) Θ(n. log2 (n)) Θ(n2 ) Θ(n3 ) Θ(2n )
10 10−8 3, 32.10−8 10−7 3, 32.10−7 10−6 10−5 10−5
103 10−8 9, 97.10−8 10−5 9, 97.10−5 10−2 10 1, 07.10293
106 10−8 1, 99.10−7 10−2 0, 199 104 1010 N/A
109 10−8 2, 99.10−7 10 298, 97 1010 1019 N/A

105 ≈ 27.7 heures

1010 ≈ 317 ans
1019 ≈ 317.109 ans
1, 07.10293 ≈ 3.39285 ans
Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 18 / 39
 Croissance comparée de quelques classes de complexité

(a) (b)
Figure – Croissance comparée de quelques classes de complexité. Les échelles de
(a) et (b) varient.

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 19 / 39
 Application aux exemples

existe : Θ(n)
uniques : Θ(n2 ), en posant k = α.n, 0 < α < 1 et par applications
des facteurs de la définition
uniques rapide : Θ(n.log2 (n)), en appliquant
Θ(n. log2 (n)) + Θ(n) = Θ(n. log2 (n))

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 20 / 39
 Complexité au meilleur cas, en moyenne, au pire cas
Algorithme 5 : Teste l’existence d’une valeur dans un tableau.
1 fonction existe sentinelle(e : Élément, t : Tableau) : Booléen
entrée : e : élément recherché
t : tableau dans lequel on recherche l’élément e
sortie : existe : vrai si l’élément e existe dans le tableau t, faux
sinon
2 existe ← Faux
3 i←0
4 tant que i < (longueur(t) - 1) et non existe faire
5 si t[i] = e alors
// Élément trouvé
6 existe ← Vrai
7 fin
8 fin
9 retourner existe
10 fin

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 21 / 39
 Complexité au meilleur cas, en moyenne, au pire cas

On cherche les conditions dans la nature des données qui influencent le

nombre d’instructions exécutées, et donc la complexité. Ces conditions
doivent être vraies pour toutes les valeurs de la taille du problème.

Définitions :
Complexité au meilleur cas : complexité quand les conditions qui
minimisent le nombre d’instructions exécutées = borne inférieure de
complexité
Complexité au pire cas : complexité dans les conditions qui
maximisent le nombre d’instructions exécutées = borne supérieure de
complexité
Complexité au cas moyen : complexité dans les conditions
“moyennes”, rencontrées en général

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 22 / 39
 Notes

On étudie plutôt la complexité au pire cas qui garantit une borne

maximale = on sait si l’algorithme peut raisonnablement s’exécuter
ou non.
Souvent, la complexité au pire et la complexité en moyenne sont les
mêmes

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 23 / 39
 Retour sur les exemples

existe sentinelle :
▶ meilleur cas :
▶ cas moyen :
▶ pire cas :

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 24 / 39
 Retour sur les exemples

existe sentinelle :
▶ meilleur cas : Θ(1)
▶ cas moyen : Θ(n)
▶ pire cas : Θ(n)

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 25 / 39
 Retour sur les exemples

existe sentinelle :
▶ meilleur cas : Θ(1)
▶ cas moyen : Θ(n)
▶ pire cas : Θ(n)
uniques :
▶ meilleur cas :
▶ cas moyen :
▶ pire cas :

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 26 / 39
 Retour sur les exemples

existe sentinelle :
▶ meilleur cas : Θ(1)
▶ cas moyen : Θ(n)
▶ pire cas : Θ(n)
uniques :
▶ meilleur cas : Θ(n)
▶ cas moyen : Θ(n2 )
▶ pire cas : Θ(n2 )

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 27 / 39
 Retour sur les exemples

existe sentinelle :
▶ meilleur cas : Θ(1)
▶ cas moyen : Θ(n)
▶ pire cas : Θ(n)
uniques :
▶ meilleur cas : Θ(n)
▶ cas moyen : Θ(n2 )
▶ pire cas : Θ(n2 )
uniques rapide
▶ meilleur cas :
▶ cas moyen :
▶ pire cas :

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 28 / 39
 Retour sur les exemples

existe sentinelle :
▶ meilleur cas : Θ(1)
▶ cas moyen : Θ(n)
▶ pire cas : Θ(n)
uniques :
▶ meilleur cas : Θ(n)
▶ cas moyen : Θ(n2 )
▶ pire cas : Θ(n2 )
uniques rapide (dépend en fait de l’algorithme de tri employé) :
▶ meilleur cas : Θ(n. log2 (n))
▶ cas moyen : Θ(n. log2 (n))
▶ pire cas : Θ(n. log2 (n))

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 29 / 39
 Processus de calcul de complexité pour un algorithme

Complexité en temps :
Choisir une (ou plusieurs) instruction(s) représentative(s) = la (ou
les) plus exécutée(s) → on sait qu’asymptotiquement les autres
seront non significatives
Compter le nombre de fois que l’instruction s’exécute au meilleur cas,
au cas moyen et au pire cas
Se rapprocher de l’expression d’une complexité standard
▶ Identifier les variables qui peuvent s’exprimer en fonction d’autres
▶ Éliminer les termes asymptotiquement non significatifs / non dominants
▶ Au besoin, démontrer à partir des définitions des notations

Complexité en espace :
Identique mais identifier les variables les plus représentées et l’espace
mémoire qu’elles consomment

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 30 / 39
 Pièges

Chercher des bornes “au plus juste” (e.g., tout algo est en Ω(1) mais
ça ne nous apprend rien. . .)
Abus de notation courant : O(g (n)) utilisé pour signifier Θ(g (n))

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 31 / 39
 Introduction au TP suivant : organisation

1 créneaux d’1h30
Lecture des codes fournis
Calcul des temps d’exécutions
Écriture d’algorithme sur papier
Programmation Python d’algorithmes

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 32 / 39
 Introduction au TP suivant : organisation

Remplissez les fonctions nécessaires.

Guettez le commentaire # TODO !
Testez systématiquement chacune de vos fonctions au fur et à mesure
de leur implémentation !

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 33 / 39
 Introduction au TP suivant : le calcul des temps
d’exécution

Dans le prochain TP, nous nous efforcerons à calculer les temps

d’exécution de codes Python dans l’objectif de vérifier empiriquement les
complexité algorithmiques calculés en TD.

Pour cela, nous utiliserons la bibliothèque time → import time.

La fonction [Link]() renvoie le temps en secondes depuis le point de

départ du temps (le 1er janvier 1970 à 00 :00 :00) pour toutes les
plateformes, sous forme de nombre à virgule flottante.

Astuce ! Si on appelle [Link]() juste avant et juste après l’appel à une

fonction f et que l’on soustrait les deux valeurs, on calcule alors le temps
d’exécution de f.

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 34 / 39
 Introduction au TP suivant : exemple

import time

def f(n):
for i in range(n):
print(‘Bip’)

t1 = [Link]()
f(500)
t2 = [Link]()
texec=t2-t1
print(‘Temps d\’exécution :’, texec,‘ secondes’)

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 35 / 39
 Introduction au TP suivant : le tracé de courbes
Pour évaluer correctement la complexité des algorithmes, il faut calculer
les temps d’exécution des programmes avec plusieurs valeurs de n,
permettant de voir si la courbe se rapproche d’une classe de complexité
connue (n, n2 , log(n), exp(n), etc.).

Pour tracer des courbes en Python, nous utiliserons la bibliothèque

[Link]. Pour simplifier l’écriture, nous utiliserons un alias à
l’aide du mot clé as tel que :

import [Link] as plt

Pour tracer une courbe, on utilisera la fonction plot de plt :

[Link](x,y)

Enfin, il faut afficher la fenêtre graphique avec :

[Link]()

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 36 / 39
 Introduction au TP suivant : exemple complet

import [Link] as plt

import numpy

x = range(50)
y1 = [Link](x)
y2 = [Link](x)

[Link](x, y1)
[Link](x, y2)

[Link]()

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 37 / 39
 Introduction au TP suivant : réflexions

Temps effectif que le processeur a passé à exécuter le code (appelé

CPU time) ̸= du temps réel (wall time).
→ le processus exécutant le code ne s’exécute pas en continu (i.e.,
partage du processeur, disques, mémoire avec d’autres processus).

Les temps d’exécution d’un code varier d’une exécution à l’autre !

Notable quand le temps d’exécution mesuré est court.
Raison : facteurs liés au fonctionnement interne de la machine.
Solution : mesurer le temps de n exécutions de la fonction, puis en
déduire une durée moyenne, pour avoir des données plus fiables.

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 38 / 39
 Des questions ?

Module INF301 - IMT Nord Europe (IMT NE) CP2 - Algorithmique 17 août 2023 39 / 39