LA COMPLEXITÉ
ALGORITHMIQUE
Chapitre 1 :
1
I- Définition :
La complexité d’un algorithme: est une mesure
évaluant la performance d’un algorithme en
fonction de la quantité de ressources (en temps
et en espace). On distingue :
La complexité en temps : temps nécessaire a
l’exécution d’un algorithme
La complexité en espace: taille mémoire
nécessaire à l’exécution d’un algorithme 2
En informatique, on s'intéresse généralement à la
complexité en temps d’un algorithme que, par abus de
langage, nous appellerons simplement "complexité d’un
algorithme"
on considère les mesures de complexités suivantes :
- Meilleur cas (cas le plus favorable) : C’est la valeur
minimale de la complexité d’un algorithme mesurée sur
toutes les entrées possibles.
- Cas moyenne : la valeur moyenne de la complexité
en considérant toutes les entrées possibles
- Le pire des cas (cas le plus défavorable) : Considère la
complexité maximale de l'algorithme sur toutes les
entrées possibles.
3
II- Déterminer le coût d’un algorithme :
Pour déterminer le coût d’un algorithme, on se
fonde en général sur le modèle de complexité
suivant :
1
Une affectation, une comparaison ou
l’évaluation d’une opération arithmétique ayant
en général un faible temps d’exécution, celui-ci
sera considéré comme l’unité de mesure du
coût d’un algorithme.
4
II- Déterminer le coût d’un algorithme :
Soit p et q deux instructions;
2
Le coût des instructions p et q en séquence est la
somme des coûts de l’instruction p et de
l’instruction q.
3
Pour un test :
if b: Le coût est inférieur ou égal au
p maximum des coûts des instructions
else: p et q, plus le temps d’évaluation
q de l’expression b. 5
II- Déterminer le coût d’un algorithme :
Pour une boucle for :
4
for i in iterable: Le coût est égal au nombre
p d’éléments de l’itérable multiplié
par le coût de l’instruction p
5
Pour une boucle while :
while condition : On majore le nombre de répétitions
p de la boucle ainsi que le coût de p
6
Application 1 :
Calculer la complexité du programme suivant :
nb= int(input('Donnez le nombre de livres: '))
if nb<10 :
prix=nb*10
else :
prix=nb*9
print('Le prix total est : ',prix)
7
Solution :
2 nb= int(input('Donnez le nombre de livres: '))
1 if nb<10 :
2 prix=nb*10
else :
prix=nb*9
1 print('Le prix total est : ',prix)
Total : 6
Ici nous avons une complexité constante. 8
Application 2 :
Calculez la complexité :
n= int(input("Donnez un entier : "))
Total=0
while n>0 :
Total+=n
n-=1
print(Total)
9
Solution :
2 n= int(input("Donnez un entier : "))
1 Total=0
n + 1 while n>0 :
4n Total+=n
n-=1
1 print(Total)
Total : 5n+5
Ici nous avons une complexité qui dépend de n. 10
III- Notation O :
1- Introduction :
En réalité, lorsqu’on cherche à évaluer l’efficacité d’un
algorithme, il est souvent inutile de calculer
exactement le nombre d'opérations élémentaires, mais
on se contente de dire que ce nombre est
proportionnel à n ,n² ou ln(n),…etc.
Par exemple, si on a déterminé que la complexité est
égale à: n2+3n, dès que la taille n des données devient
un peu importante, il est connu que le terme 3n
augmente beaucoup moins vite que n2 : on dit qu’il est
négligeable devant ce dernier.
Pour décrire l’efficacité d’un algorithme, seul le terme
qui croît le plus vite a donc un intérêt. 11
Par exemple :
Pour n ≥ 3, on a : n2+3n ≤ 2n2
la quantité n2+3n est donc bornée, à partir d’un
certain rang, par le produit de n2 et d’une
constante.
On dit alors que la quantité de n2 + 3n est « un
grand O de n2 » et on écrira n2 + 3n = O(n2).
12
2- Définition :
Soient f et g deux fonctions de N dans R+
On dit que f = O(g) (qui se prononce f est un grand O
de g) s'il existe une constante c et une constante
entière (seuil) n0 ≥1 telle que :
f(n) ≤ c*g(n) pour tout entier n ≥ n0
f = O(g) signifie que f est dominée asymptotiquement par g.
13
3- Propriétés :
La notation O, dite notation de Landau, vérifie les
propriétés suivantes :
◦ Si f=O(g) et g=O(h) alors f=O(h)
◦ Si f=O(g) et k un nombre, alors k*f=O(g)
◦ Si f1=O(g1) et f2=O(g2) alors f1+f2 = O(g1+g2)
◦ Si f1=O(g1) et f2=O(g2) alors f1*f2 = O(g1*g2)
14
Applications
Quel est l'ordre de grandeur pour chacun des cas
suivants :
100
2N+5
50N+N²
6N3+N+100+3N²
2N²+5N+3N² +8
50N+N ln(N)
15
Applications
◦
16
4- Cas généraux :
Notation Dénomination Exemples d'application
O(1) Constante Opération indépendante de l'entrée
Notation Dénomination Exemples d'application
O(ln n) Logarithmique Recherche dichotomique
O(1)
O(n) Constante
Linéaire Opération
Parcours indépendante
d'une liste de l'entrée
O(ln n) Logarithmique Recherche dichotomique
O(n ln n) Quasi-lineaire qlq Algorithme de tri
O(n) Linéaire Parcours d'une liste
O(n²) Quadratique qlq Algorithme de tri
O(n ln n) Quasi-lineaire qlq Algorithme de tri
O(n 3) Cubique Produit matricielde tri
O() Quadratique qlq Algorithme
O() Cubique Triple boucles imbriquée
O(2n) Exponentielle Suite Fibonacci
O() Polynomiale K boucles imbriquée
17
4- Cas généraux :
En s’appuyant sur une base de 109 opérations par seconde et pour une taille
de données (n= 106):
Complexit Temps d’exécution
é
O(1) 1 ns
O(ln n) 14 ns
O(n) 1 ms
O(n ln n) 14 ms
O(n²) 16.66 min
O(n3) 31.6 années
O(2n) A vous de la calculer
18
IV- Etude d'un cas :
19
def puiss1(x,n) :
1 res = 1
n+1 while n > 0 :
4n res *= x
n -= 1
1 return res
Total : 5n + 2
Donc O(n)
20
On peut calculer la complexité autrement :
def puiss1(x,n) :
res = 1 O(1)
while n > 0 :
res *= x O(n)
n -= 1
return res O(1)
La complexité de cette fonction est donnée par :
O(1) + O(n) + O(1) = O(n)
21
2- Méthode 2 :
def puiss2(x,n) :
if n==0 :
return 1
else :
return x*puiss2(x,n-1)
Remarque :
Pour une fonction récursive :
Complexité = Coût d’une seule exécution de la fonction
+
Coût des appels récursifs 22
Soit t(n) le nombre d'opérations élémentaires
nécessaire à l'exécution du programme :
t(n)= 3 + t(n-1) Relation de récurrence
= 3 + 3 + t(n-2)
Donc à l'étape k:
t(n) = 3k+t(n-k)
La récurrence s'arrêtera lorsque : n-k=0 donc k=n.
t(n) = 3n + t(0)
= 3n+ 1
D’où O(n) 23
Méthode 3 :
def puiss3(x,n) :
if n==1 :
return x
elif n%2==0 :
return puiss3(x*x,n/2)
else :
return x*puiss3(x,n-1)
24
• Si n est pair : t(n)=5+t(n/2)
• Si n est impair: t(n)=5 + t(n-1) = 10 + t(n/2)
t(n) = 10 + t(n/2)
t(n) = 10 + 10 + t(n/4) càd 2*10 + t(n/22)
t(n) = 10 + 10 + 10+ t(n/8) càd 3*10 + t(n/23)
t(n) = 10k + t(n/2k)
On s'arrêtera quand : n/2k = 1 donc k = log2(n)
t(n)= 10 log2(n)+t(1)
D’où O(log2(n))
CONCLUSION :
Méthode 1 Méthode 2 Méthode 3
O(n) O(n) O(ln(n))
La méthode 3 (Exponentiation Binaire)
est la méthode la plus rapide pour
calculer xn
26
Fonctions prédéfinies
Soit ls une liste de n valeurs
Fonction Complexité
[Link] O(1)
[Link] O(n)
[Link] O(n)
Slicing (k éléments) O(k)
x in ls O(n)
len(ls) O(1)
max(ls), min(ls) O(n)
[Link](-1) (dernier elt) O(1)
[Link](i) (position qlq) O(n)
IV- Complexité en espace:
On appelle complexité en espace d’un
algorithme la place nécessaire en mémoire pour
le faire fonctionner. Elle s’exprime également sous
la forme d’un O(f(n)) où n est la taille du
problème.
Évaluer la complexité en espace d’un algorithme
ne pose pas de difficulté; il suffit de faire le total
des tailles en mémoire des différentes variables
utilisées
28
Application :
def sommePolynome(P,Q) :
n = len(P)
R = [0] * n
for i in range(n) :
R[i] = P[i] + Q[i]
return R
Calculer la complexité en espace de la fonction suivante.
On suppose que les deux listes P et Q représentent deux
polynômes dont le degré est le même
29
- Les listes P, Q et R ont une dimension: n + n + n = 3n
- La fonction utilise 2 variable (n et i) : 2
Au total : 3n + 2
D’où :
O(n)
30
Application : (Centrale supélec 2016)
Après avoir récupéré les informations nécessaires, la fonction
acquerir_intrus calcule la position et la vitesse de l’intrus par rapport à
l’avion propre et renvoie une liste de huit nombres : [id, x, y, z, vx, vy, vz, t0],
où :
− id est le numéro d’identification de l’intrus ;
− x, y, z les coordonnées (en mètres) de l’intrus dans un repère orthonormé
R0 lié à l’avion propre ;
− vx, vy, vz la vitesse (en mètres par seconde) de l’intrus dans ce même
repère ;
− t0 le moment de la mesure (en secondes depuis un instant de référence).
À des fins d’analyse une fois l’avion revenu au sol, la fonction
acquerir_intrus conserve chaque résultat obtenu. Chaque nombre est
stocké sur 4 octets. En supposant que cette fonction est appelé au maximum
100 fois par seconde, quel est le volume de mémoire nécessaire pour
conserver les données de 100 heures de fonctionnement ?
Ce volume de stockage représente-t-il une contrainte technique forte ?
Nous avons 8 variables. Chacune est codée sur 4 octets ce qui fait au total :
32 bits
Durant 100h de fonctionnement la fonction acquerir_intrus sera appelé
100 fois par second. Le nombre total des appels est donc :
100*100*3600
La taille de la mémoire nécessaire sera donc la taille des variables
multipliée par le nombre de fois que la fonction sera utilisée, soit :
32 * 100 * 100 * 3600 = 1152000000 octets = 1.152 GO
Cette taille est largement raisonnable vu l’avancement technologique
actuel
