18/10/2020

ETUDE DE LA

COMPLEXITE

PLAN
 Introduction

 Définitions

 Type de la Complexité

 Notation de de Landau

 Classes de complexité
 Calcul de la Complexité des algorithmes (itératifs
& récursifs)
3

1
 18/10/2020

INTRODUCTION
ANALYSES D’ALGORITHMES

Input Algorithme Output

Un algorithme est une procédure étape par étape

pour résoudre un problème dans un temps fini.

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
4
l’algorithme doit traiter.

2
 18/10/2020

INTRODUCTION
TEMPS D’EXECUTION

• Les algorithmes transforment des best case

objets en entrée en des objets en average case
sortie. worst case
120
• Le temps d’exécution d’un
algorithme croît en fonction de la 100

taille des entrées.

Running Time
80
• Le temps d’exécution en moyenne
60
est souvent difficile à déterminer.
• Nous nous intéresserons au pire cas 40

dans le temps d’exécution. 20

• Facile à analyser
0
• Crucial dans les applications dans 1000 2000 3000 4000
le domaine des jeux, des Input Size
finances et de la robotique par
exemple.

INTRODUCTION
ETUDES EXPERIMENTALES

9000
• Écrire un programme implémentant
8000
un algorithme
• Exécuter le programme avec 7000
différentes tailles des données en 6000
entrée.
Time (ms)

5000
• Utiliser une fonction, comme la
fonction prédéfinie clock(), pour 4000
avoir une mesure des temps
3000
d’exécution.
2000
• Tracer les résultats.
1000

0
0 50 100
Input Size

3
 18/10/2020

INTRODUCTION
LIMITATION DES EXPERIENCES

• Il est nécessaire d’implémenter l’algorithme, ce qui peut être difficile.

• Les résultats peuvent ne pas être indicatifs du temps d’exécution
d’autres entrées non inlcuses dans l’expérience.
• Pour comparer deux algorithmes, le même environnement de
programmation (matériel et logiciel) doit être utilisé.

INTRODUCTION
ANALYSE THEORIQUE

• Utiliser une description de haut niveau de l’algorithme au lieu de

l’implémenter.
• Caracteriser le temps d’exécution comme une fonction de la taille des
entrées, n.
• Tenir compte de toutes les possibilités comme entrée.
• Nous permet d’évaluer la vitesse d’un algorithme independemment de
l’environnement.

4
 18/10/2020

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[0..n]d’entier,

5
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
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
6
Au moins 3 variables 3 variables

10

5
 18/10/2020

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 + a 0

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
7
2 variables
FP
Fin
11

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 e8t
l’implémenter
12

6
 18/10/2020

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 et meilleur qu’un algorithme B indépendamment
de la machine, du langage de programmation,

du compilateur et des détails d’implémentation. 9

13

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 10

14

7
 18/10/2020

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 to1u1t n
> n0 T(n) <= c n2
15

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) 12

16

8
 18/10/2020

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.
13
Ceci explique les règles de la notation O.

17

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

18

9
 18/10/2020

CLASSES DE COMPLEXITÉ

15

19

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)) .

16

20

10
 18/10/2020

CALCUL DE LA COMPLEXITÉ
 Exemple 1:

Permutation (Var S: tableau [0..n-1] d’entier, i, j: entier)

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

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

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

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

17

21

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.

18

22

11
 18/10/2020

CALCUL DE LA COMPLEXITÉ

19

23

CALCUL DE LA COMPLEXITÉ
5. Cas de boucles imbriquées:

 Les deux compteurs sont  Les deux compteurs sont

indépendants dépendants

int j,k; int j,k;

for (j=0; j<N; j++) for (j=0; j < N; j++)
for (k=N; k>0; k--) for (k=0; k < j; k++)
sum += k+j; sum += k+j;

Commencez par la boucle extérieure: Analysez les boucles interne et externe

- Combien d'itérations? N ensemble:
- Combien de temps par itération? Besoin - Le nombre d'itérations de la boucle interne
d'évaluer la boucle intérieure est:
La complexité de la boucle intérieure est 0 + 1 + 2 + ... + (N-1) = O (N2)
18
O(N)
Complexité totale est N * O(N) = O(N*N) =
O(N2) 24

12
 18/10/2020

CALCUL DE LA COMPLEXITÉ

 Exemple 2:
• Recherche séquentielle (S: tableau [0..n-1] d’entier, x: entier): booléen

• i 0 c1
• Trouve  faux c2
Condition = c3;
• Tant que ((i<n) et (non trouve)) faire DTQ
nombre d’itération = n
• Si (S[i] = x) alors
c4
Trouve  vrai
c5
• i i + 1
c6
FTQ
• Retourner trouve
c7
T(n) = c1+c2+n*(c3+c4+c5+c6) + c7 = c8 + c9 *n 20

O(T) = O(c8 + c9 *n) = O (n)

25

CALCUL DE LA COMPLEXITÉ
 Exemple 3:
Tri par sélection (Var T: Tableau [1.. N] d’entier)

21

26

13
 18/10/2020

CALCUL DE LA COMPLEXITÉ
 Exemple 4:

22

27

CALCUL DE LA COMPLEXITÉ

 Exemple 5:

23

28

14
 18/10/2020

COMPLEXITÉ DES ALGORITHMES

RÉCURSIFS
 La complexité d’un algorithme récursif se fait par la
résolution d’une de ces équations de récurrence:

26

29

COMPLEXITÉ DES ALGORITHMES

RÉCURSIFS
 Exemple 1: la fonction factorielle
Facto (n: entier): entier Début

Si (n=1) alors retourner 1

Sinon retourner n*Facto (n-1);
Fin

27

30

15
 18/10/2020

COMPLEXITÉ DES ALGORITHMES

RÉCURSIFS
 Exemple 1: la fonction factorielle

i.e. T(n) = T(n-1) + f(n) avec a = 1, T(0) = 0, f(n) = b;

28

O (T) = O (n)
31

COMPLEXITÉ DES ALGORITHMES

RÉCURSIFS
 Exemple 2: T(n) = 2*T(n-1) + c avec T(0) = 0

O (T) = O(2n)
29

32

16
 18/10/2020

COMPLEXITÉ DES ALGORITHMES

RÉCURSIFS
 Exemple 3: Recherche du maximum.

Fonction maximum ( Tab: Tableau , indDeb, indFin:entier)

Si ( indDeb = indFin) alors retourner (indDeb)

Sinon

M(indDeb+indFin) div 2 // division du problème en 2 sous-problèmes

k1  maximum (Tab, indDeb, m ) // régner sur le 1er sous-problème

k2 maximum (Tab, m+1, indFin) // régner sur le 2ème sous-problème

// Combiner les solutions

Si (Tab[k1] > Tab[k2]) alors retourner (k1) 30

Sinon retourner (k2)

33

COMPLEXITÉ DES ALGORITHMES

RÉCURSIFS

 Exemple 3: Recherche du maximum.

T(n) = 2 T(n/2) + c

a = 2 , b = 2, k = 0  a > bk

T(n) = O(n) 31

34

17
 18/10/2020

COMPLEXITÉ DES ALGORITHMES

RÉCURSIFS
 Exemple 4: Recherche dichotomique.

Fonction RechDicho(Tab :Tableau, borneinf, bornesup, x :entier) : bool

Si (borneinf<=bornesup) alors
mil  (borneinf+bornesup) DIV 2 ;
Si (Tab[mil]=x) Alors retourner (vrai)
Sinon
Si (Tab[mil]>x) Alors
Retourner (RechDicho(Tab, borneinf, mil-1, x))
Sinon
Retourner(RechDicho(Tab, mil+1, bornesup, x))
Sinon 32

Retourner (Faux)
35

COMPLEXITÉ DES ALGORITHMES

RÉCURSIFS

 Exemple 4: Recherche dichotomique

T(n) = T(n/2) + c

a = 1 , b = 2, k = 0  a = bk
T(n) = O(log(n))

33

36

18
 18/10/2020

COMPLEXITÉ DES ALGORITHMES

RÉCURSIFS
 Exemple 5 : La suite de Fibonacci

37

37

COMPLEXITÉ DES ALGORITHMES

RÉCURSIFS
 Exemple 5 : La suite de Fibonacci

38

38

19