Université Saad Dahlab de Blida

Faculté des Sciences

Département d’Informatique
Licence d’Informatique
Semestre 3 (2ème année)
Algorithmique et Structures de Données

CHAPITRE II:
COMPLEXITÉ
Mme AROUSSI

2016-2017

Disponible sur [Link]

PLAN DU CHAPITRE II

 Introduction

 Définitions

 Type de la Complexité

 Notation de de Landau

 Classes de complexité

 Calcul de la Complexité
2
 INTRODUCTION

 Le temps d’exécution d’un algorithme dépend des facteurs

suivants :
 Les données du programme,
 La qualité du compilateur (langage utilisé),
 La machine utilisée (vitesse, mémoire, ),
 La complexité de l’algorithme lui-même,

 On cherche à mesurer la complexité d’un algorithme

indépendamment de la machine et du langage utilisés, c.-
à-d. uniquement en fonction de la taille des données que
3
l’algorithme doit traiter.
 INTRODUCTION
EXEMPLE: CALCUL DE LA VALEUR D’UN POLYNÔME

 Soit P(X) un polynôme de degré n

P(X) = anXn + an-1Xn-1 + ... + a1X + a0 ,

Où: n : entier naturel

an, an-1, ..., a1, a0 : les coefficients du polynôme qui sont

stockés dans le tableau T[0..n] d’entiers.

 Ecrire la fonction Calcul_poly(T: Tableau[n+1]d’entier,

4
X:entier): entier.
 INTRODUCTION
EXEMPLE: CALCUL DE LA VALEUR D’UN POLYNÔME
2ème variante
1ère variante
Début
Début
Inter1
P0
P 0
Pour i  0 à n faire
Pour  0 à n faire
DP
DP
P  P+ T[i] * Puiss (X, i)
P  P+ Inter *T[i]
FP
Inter  Inter * X
Fin
FP
1ère Complexité :
Fin
(n+1) additions 2ème Complexité :
(n+1) multiplications (n+1) additions
(n+1) puissances 2(n+1) multiplications
5
Au moins 3 variables 3 variables
 INTRODUCTION
EXEMPLE: CALCUL DE LA VALEUR D’UN POLYNÔME

 3ème variante: Schéma de Horner

P(X) = anXn + an-1Xn-1 + ... +a2X2 + a1X + a0
=(anXn-1 + an-1Xn-2 + ... +a2X + a1)X + a0
= ((anXn-1 + an-1Xn-2 + ... +a2)X+ a1)X + a0
= ............

= (....(((anX + an-1)X+ an-2 )X.....)X+ ... +a2)X+ a1)X + a0

3ème variante
Début
P  T[n] 3ème Complexité :

Pour i  n-1 à 0 faire n additions

P  P*X + T[i] n multiplications

6
FP 2 variables

Fin
 INTRODUCTION
EXEMPLE: CALCUL DE LA VALEUR D’UN POLYNÔME

Variantes Première Deuxième Troisième

Complexité (n+1) additions (n+1) additions n additions
en temps
(en terme de (n+1) multiplications 2(n+1) n multiplications
nombre (n+1) puissances multiplications
d’opérations)

Complexité P, i et les variables P, i et Inter P, i

en espace
mémoire de la fonction
(Variables) puissance appelée
(n+1) fois

 Nécessité d’estimer la complexité en temps et en

espace d’un algorithme avant de l’écrire et7
l’implémenter
 DÉFINITION
 La complexité (temporelle) d’un algorithme est la
mesure du nombre d’opérations fondamentales
(affectations, comparaisons, opérations arithmétiques)
qu’il effectue sur un jeu de données. Elle est exprimée
comme une fonction de la taille du jeu de données.
 Elle permet en particulier de comparer deux algorithmes traitant
le même calcul. En d’autres termes, elle permet de déterminer si
un algorithme A est meilleur qu’un algorithme B
indépendamment de la machine, du langage de programmation,
du compilateur et des détails d’implémentation. 8
 TYPE DE LA COMPLEXITÉ

Complexité au Complexité en Complexité au

meilleur moyenne pire

•C'est le plus petit nombre •C’est la moyenne des • C’est le plus grand
d'opérations qu'aura à complexités de l’algorithme nombre d’opérations
exécuter l'algorithme sur sur des jeux de données de qu’aura à exécuter
un jeu de données de taille n l’algorithme sur un jeu de
taille n. données de taille n
•Tmin(n) = mindDnT(d) •Tmoy(n) = ΣdDn T(d) / |Dn| •Tmax(n) = maxdDn T(d)

 Notations:

 Dn l’ensemble des données de taille n

 T(n) le nombre d’opération sur un jeu donnée de taille n 9

 NOTATION DE LANDAU

 La notation de Landau « O » est celle qui est le

plus communément utilisée pour expliquer
formellement les performances d'un algorithme.

 Cette notation exprime la limite supérieure d'une

fonction dans un facteur constant.

 Exemple: T(n) = O(n2) veut dire qu'il existe une

constante c > 0 et une constante n0 > 0 tel que pour tout
10

n > n0 T(n) <= c n2

 NOTATION DE LANDAU

 Les règles de la notation O sont les suivantes :

 Les termes constants : O(c) = O(1)

 Les constantes multiplicatives sont omises :

O(cT ) = c O(T) = O(T)

 L'addition est réalisée en prenant le maximum :

O(T1) + O(T2) = O(T1 + T2) = max(O(T1);O(T2))

 La multiplication reste inchangée

O(T1)O(T2) = O(T1T2) 11
 NOTATION DE LANDAU
 Supposant que le temps d'exécution d’un algorithme est décrit par la fonction
T(n) = 3n2+10n+10, Calculer O(T(n))?
O(T(n)) = O(3 n2 + 10n + 10)
= O(max (3 n2, 10n, 10))
= O(3 n2)
= O (n2)
 Remarque:
Pour n = 10 nous avons :
 Temps d'exécution de 3 n2 : 3(10)2 / 3(10)2+10(10)+10 = 73,2%
 Temps d'exécution de 10n : 10(10) / 3(10)2+10(10)+10 = 24,4%
 Temps d'exécution de 10 : 10 / 3(10)2+10(10)+10 = 2,4%
Le poids de 3 n2 devient encore plus grand quand n = 100, soit 96,7%
On peut négliger les quantités 10n et 10.
12
Ceci explique les règles de la notation O.
 NOTATION DE LANDAU

 Exercice 1 : Soient T1(n) et T2(n) les temps d'exécution

de 2 fragments de programme P1 et P2 respectivement.
Montrer les règles suivantes :

 Somme : Si T1(n) = O (f(n)) et T2(n) = O(g(n) ) alors

T1(n) + T2(n) = O(max (f(n), g(n) )

 Produit : Si T1(n) = O( f(n) ) et T2(n) = O(g(n)) Alors

T1(n) * T2(n) = O (f(n) * g(n) )

13
 CLASSES DE COMPLEXITÉ

Classe Notation O Exemple

Constante O(1) Accéder au premier élément d'un ensemble de données

Linéaire O(n) Parcourir un ensemble de données

Logarithmique O(log(n)) Couper un ensemble de données en deux parties égales,

puis couper ces moitiés en deux parties égales, etc.

Quasi-linéaire O(n log(n)) Couper répétitivement un ensemble de données en deux

et combiner les solutions partielles pour calculer la
solution générale
Quadratique O(n2) Parcourir un ensemble de données en utilisant deux
boucles imbriquées

Polynomiale O(nP) Parcourir un ensemble de données en utilisant P

boucles imbriquées

Exponentielle O(an) Générer tous les sous-ensembles possibles

d'un ensemble de données
14
CLASSES DE COMPLEXITÉ

15
 CLASSES DE COMPLEXITÉ

 Exercice 2 : Compléter les tableaux suivants sachant que :

 Dans le tableau (a), il s'agit de calculer le nombre

d'opérations nécessaire pour exécuter l'algorithme en
fonction de sa complexité et de la taille d'instance du
problème traité.

16
 CLASSES DE COMPLEXITÉ

 Exercice 2 : Compléter les tableaux suivants sachant que :

 Dans le tableau (a), il s'agit de calculer le nombre

d'opérations nécessaire pour exécuter l'algorithme en
fonction de sa complexité et de la taille d'instance du
problème traité.

17
 CLASSES DE COMPLEXITÉ

 Exercice 2 : Compléter les tableaux suivants sachant que :

 Dans le tableau (b), il s'agit de calculer le temps

nécessaire à cela en supposant que l'on dispose d'un
ordinateur capable de réaliser 109 opérations par
seconde.

18
 CLASSES DE COMPLEXITÉ

 Exercice 2 : Compléter les tableaux suivants sachant que :

 Dans le tableau (c), on calcule la plus grande instance de

problème traitable dans le temps imparti.

19
 CLASSES DE COMPLEXITÉ

 Exercice 2 (Solution):.

20
 CLASSES DE COMPLEXITÉ

 Exercice 2 (Solution):.

21
 CALCUL DE LA COMPLEXITÉ

1. Cas d'une instruction simple (écriture, lecture, affectation ) :

Le temps d'exécution de chaque instruction simple est O(1).

2. Cas d'une suite d'instructions simples: Le temps d ’exécution

d'une séquence d'instruction est déterminée par la règle de la
somme. C'est donc le temps de la séquence qui a le plus grand
temps d ’exécution: O(T) = O (T1 + T2) = max(O(T1);O(T2)) .

22
 CALCUL DE LA COMPLEXITÉ

 Exemple 2:
Permutation (Var S: tableau [n] d’entier, i, j: entier)

tmpS[i] O(T1) = O(1)

S[i]S[j] O(T2) = O(1)

O(T3) = O(1)
S[j]tmp

O(T) = O (T1 + T2 + T3) = O(1)

23
 CALCUL DE LA COMPLEXITÉ

3. Cas d'un traitement conditionnel: Le temps d'exécution d'une

instruction SI est le temps d ’exécution des instructions exécutées
sous condition, plus le temps pour évaluer la condition. Pour une
alternative, on se place dans le cas le plus défavorable.

24
 CALCUL DE LA COMPLEXITÉ

4. Cas d'un traitement itératif : Le temps d ’exécution d'une boucle

est la somme du temps pour évaluer le corps et du temps pour
évaluer la condition. Souvent ce temps est le produit du nombre
d'itérations de la boucle par le plus grand temps possible pour une
exécution du corps.

Boucle Pour Boule Tant que

25
 CALCUL DE LA COMPLEXITÉ

 Exemple 2:

Recherche séquentielle (S: tableau [n] d’entier, x: entier): booléen

i 0 O(1)
Trouve  faux O(1)
Tant que ((i<n) et (non trouve)) faire Condition = O(1);
DTQ nombre d’itération = n

Si (S[i] = x) alors O(1)

Trouve  vrai O(1)
i i + 1 O(1)
FTQ
Retourner trouve Q(1)
O(T) = max(O (1) + O (n *1) + O(1)) = O (n) 26
 CLASSES DE COMPLEXITÉ

 Exercice 3: Considérer les algorithmes suivants avec un

temps d’exécution T(n) pour une longueur de données n.
Déterminer leur complexité et les classer par ordre croissant

 Algorithme A1 T(n) = 3n+2

 Algorithme A2 T(n) = 6

 Algorithme A3 T(n) = 4n2+n+2

 Algorithme A4 :

Pour i1 à n faire Exécuter A3

27

Exécuter A1
 CLASSES DE COMPLEXITÉ

 Exercice 3 (suite): Considérer les algorithmes suivants

avec un temps d’exécution T(n) pour une longueur de
données n. Déterminer leur complexité et les classer par
ordre croissant

 Algorithme A5 :

Exécuter A1 ; Exécuter A2 ; Exécuter A3 ;

 Algorithme A6

Pour i1 à 5 faire Exécuter A1

28
 CLASSES DE COMPLEXITÉ

 Exercice 4: Calculer la complexité au pire des algorithmes

suivants :

a) Pour i  1 à n faire Op

b) Pour i 0 à n faire Op

c) Pour i 0 à n-1 faire

Op1

Pour j0 à n-1 faire Op2

29
 CLASSES DE COMPLEXITÉ

 Exercice 4 (suite): Calculer la complexité au pire des

algorithmes suivants :
d) Pour i 0 à n-1 faire
Op1
Pour j0 à n-1 faire
Op2
Pour k0 à n-1 faire Op3
e) Pour i 0 à n-1 faire
Op1
Pour j1 à i faire Op2 30
 CLASSES DE COMPLEXITÉ

 Exercice 4 (suite): Calculer la complexité au pire des

algorithmes suivants :

f) Tant que (n > 0) faire

Op

nn/2

g) Pour i0 à n faire

Si i%2 = 0 alors Op1

Sinon 31

Pour j0 à n faire Op2

 CLASSES DE COMPLEXITÉ

 Exercice 4 (suite): Calculer la complexité au pire des

algorithmes suivants :

h) Pour i0 à n faire i) Pour i0 à n faire

Op1 Op1
j 1 j1
Répéter Répéter
Op2 Op2
jj+3 jj*3 32

jusqu’à j >i jusqu’à j >n

 CLASSES DE COMPLEXITÉ

 Exercice 4 (suite): Calculer la complexité au pire des

algorithmes suivants :

k 1

Répéter

j1

Tant que (j ≤n) faire jj*10

k k+2

jusqu’à (k ≤n) 33
 SOURCES DE CE COURS
 Frédéric Vivien, Algorithmique avancée, École Normale Supérieure de Lyon, 2002.,
pp. 93. Disponible sur [Link]
2001-2002/[Link]

 Slim Msfar, Algorithmique et Complexité, 2012, pp 104. Disponible sur

[Link]

 Djamel-Eddine ZEGOUR, O-Notation, École nationale Supérieure d’Informatique,

pp 33. Disponible sur
[Link]

34