Chapitre 2 :

complexité temporelle
1) Intuition
2) Comparaison asymptotique
3) Taille de l'entrée, opérations élémentaires
4) Ordre de grandeur
5) Complexité en pire cas
6) Exemples

1
 1) Intuition
●Un algorithme ne s'exécute pas de manière
instantanée.
●Chaque instruction prend un certain temps à être
exécutée, même si ce temps-là est très petit sur les
ordinateurs.
●Lorsque l'on exécute notre algorithme à la main, on se
bien rend compte que certains algorithmes sont plus
rapides que d'autres, même s'ils répondent à la même
question.
2
 1) Intuition
●Exemple: une fonction qui prend en argument un
entier n et qui renvoie la somme des entiers de 1 à n.
Solution 1 Solution 2
Fun int somme1(int n):
Fun int somme2(int n):
int s:=0
int s:=n*(n+1)
int i
s:=s/2
Pour i allant de 1 à n:
Renvoyer s
s:=s+i
Renvoyer s

● Comptons le nombre d'affectations effectuées.

3
 Exécution de la solution 1
Fun int somme1(int n):
int s:=0
int i
Pour i allant de 1 à n:
s:=s+i
Renvoyer s
Début
int S
S:=somme1(4) Affichage en console
print("S vaut", S)
4

Fin
 Exécution de la solution 1
Fun int somme1(int n):
int s:=0
int i
Pour i allant de 1 à n:
s:=s+i
Renvoyer s
Variables du prog. princ.
Début
S (int)
int S
Début
S:=somme1(4) Affichage en console
print("S vaut", S)
5

Fin
 Exécution de la solution 1
Fun int somme1(int n):
int s:=0
int i
Pour i allant de 1 à n:
s:=s+i
Renvoyer s
Variables du prog. princ.
Début
S (int)
int S
S:=somme1(4) Affichage en console
print("S vaut", S)
6

Fin
 Exécution de la solution 1
Fun int somme1(int n): Variables de somme1
int s:=0 n 4
(int) 0
int i
Pour i allant de 1 à n:
s:=s+i Nombre d'affectations
0
jusqu'ici dans somme1:
Renvoyer s
Variables du prog. princ.
Début
S (int)
int S
S:=somme1(4) Affichage en console
print("S vaut", S)
7

Fin
 Exécution de la solution 1
Fun int somme1(int n): Variables de somme1
int s:=0 n 4

int i
s(int)
(int) 0

Pour i allant de 1 à n:
s:=s+i Nombre d'affectations
l
jusqu'ici dans somme1:
Renvoyer s
Variables du prog. princ.
Début
S (int)
int S
S:=somme1(4) Affichage en console
print("S vaut", S)
8

Fin
 Exécution de la solution 1
Fun int somme1(int n): Variables de somme1
int s:=0 n 4

int i
s(int)
(int) 0
i (int)
Pour i allant de 1 à n:
s:=s+i Nombre d'affectations
l
jusqu'ici dans somme1:
Renvoyer s
Variables du prog. princ.
Début
S (int)
int S
S:=somme1(4) Affichage en console
print("S vaut", S)
9

Fin
 Exécution de la solution 1
Fun int somme1(int n): Variables de somme1
int s:=0 n 4

int i
s(int)
(int) 0
i (int) 1
Pour i allant de 1 à n:
s:=s+i Nombre d'affectations
ll
jusqu'ici dans somme1:
Renvoyer s
Variables du prog. princ.
Début
S (int)
int S
S:=somme1(4) Affichage en console
print("S vaut", S)
10

Fin
 Exécution de la solution 1
Fun int somme1(int n): Variables de somme1
int s:=0 n 4

int i
s(int)
(int) 1
i (int) 1
Pour i allant de 1 à n:
s:=s+i Nombre d'affectations
lll
jusqu'ici dans somme1:
Renvoyer s
Variables du prog. princ.
Début
S (int)
int S
S:=somme1(4) Affichage en console
print("S vaut", S)
11

Fin
 Exécution de la solution 1
Fun int somme1(int n): Variables de somme1
int s:=0 n 4

int i
s(int)
(int) 1
i (int) 2
Pour i allant de 1 à n:
s:=s+i Nombre d'affectations
llll
jusqu'ici dans somme1:
Renvoyer s
Variables du prog. princ.
Début
S (int)
int S
S:=somme1(4) Affichage en console
print("S vaut", S)
12

Fin
 Exécution de la solution 1
Fun int somme1(int n): Variables de somme1
int s:=0 n 4

int i
s(int)
(int) 3
i (int) 2
Pour i allant de 1 à n:
s:=s+i Nombre d'affectations
lllll
jusqu'ici dans somme1:
Renvoyer s
Variables du prog. princ.
Début
S (int)
int S
S:=somme1(4) Affichage en console
print("S vaut", S)
13

Fin
 Exécution de la solution 1
Fun int somme1(int n): Variables de somme1
int s:=0 n 4

int i
s(int)
(int) 3
i (int) 3
Pour i allant de 1 à n:
s:=s+i Nombre d'affectations
llllll
jusqu'ici dans somme1:
Renvoyer s
Variables du prog. princ.
Début
S (int)
int S
S:=somme1(4) Affichage en console
print("S vaut", S)
14

Fin
 Exécution de la solution 1
Fun int somme1(int n): Variables de somme1
int s:=0 n 4

int i
s(int)
(int) 6
i (int) 3
Pour i allant de 1 à n:
s:=s+i Nombre d'affectations
lllllll
jusqu'ici dans somme1:
Renvoyer s
Variables du prog. princ.
Début
S (int)
int S
S:=somme1(4) Affichage en console
print("S vaut", S)
15

Fin
 Exécution de la solution 1
Fun int somme1(int n): Variables de somme1
int s:=0 n 4

int i
s(int)
(int) 6
i (int) 4
Pour i allant de 1 à n:
s:=s+i Nombre d'affectations
llllllll
jusqu'ici dans somme1:
Renvoyer s
Variables du prog. princ.
Début
S (int)
int S
S:=somme1(4) Affichage en console
print("S vaut", S)
16

Fin
 Exécution de la solution 1
Fun int somme1(int n): Variables de somme1
int s:=0 n 4

int i
s(int)
(int) 10
i (int) 4
Pour i allant de 1 à n:
s:=s+i Nombre d'affectations
lllllllll
jusqu'ici dans somme1:
Renvoyer s
Variables du prog. princ.
Début
S (int)
int S
S:=somme1(4) Affichage en console
print("S vaut", S)
17

Fin
 Exécution de la solution 1
Fun int somme1(int n): Variables de somme1
int s:=0 n 4

int i
s(int)
(int) 10
i (int) 4
Pour i allant de 1 à n:
Valeur de retour:
s:=s+i 10 d'affectations
Nombre
lllllllll
jusqu'ici dans somme1:
Renvoyer s
Variables du prog. princ.
Début
S (int)
int S
S:=somme1(4) Affichage en console
print("S vaut", S)
18

Fin
 Exécution de la solution 1
Fun int somme1(int n):
int s:=0 4
10
int i
4
Pour i allant de 1 à n:
s:=s+i Nombre d'affectations au
lllllllll =9 affectations
total dans somme1:
Renvoyer s
Variables du prog. princ.
Début
S (int) 10
int S
S:=somme1(4) Affichage en console
print("S vaut", S)
19

Fin
 Exécution de la solution 1
Fun int somme1(int n):
int s:=0 4
10
int i
4
Pour i allant de 1 à n:
s:=s+i Nombre d'affectations au
lllllllll =9 affectations
total dans somme1:
Renvoyer s
Variables du prog. princ.
Début
S (int) 10
int S
S:=somme1(4) Affichage en console
print("S vaut", S) S vaut 10
20

Fin
 1) Intuition
●La solution 1 a nécessité 9 affectations, alors que la
solution 2 aurait nécessité seulement 2 affectations.
●Plus généralement, comptons combien d'affectations
seront faites en fonction de la valeur du paramètre n.
Solution 1
Fun int somme1(int n):
int s:=0 1 aff.
int i 2 affectations à chaque fois
Pour i allant de 1 à n: que l'on passe dans la boucle:
s:=s+i une pour i et une pour s
Renvoyer s
On passe n fois dans la boucle
21
Total: 2n+1 affectations
 1) Intuition
●La solution 1 a nécessité 9 affectations, alors que la
solution 2 aurait nécessité seulement 2 affectations.
●Plus généralement, comptons combien d'affectations
seront faites en fonction de la valeur du paramètre n.
Solution 2
Fun int somme2(int n): La solution numéro 2 a donc
int s:=n*(n+1) 1 aff. l'air plus rapide, surtout si
s:=s/2 l'entrée n devient grande!
1 aff.
Renvoyer s

Total: 2 affectations
22
 1) Intuition
●La fréquence d'un processeur désigne le nombre
d'opérations qui sont effectuées en une seconde.
●Par exemple, la fréquence du processeur de mon
ordinateur est 1.8GHz=1.8 x 109 Hz donc 1.8 milliards
d'opérations par seconde.
●Une opération prend donc environ 0.5 x 10-9 sec, c'est-
à-dire 0.5 nanoseconde.
●Supposons que, pour résoudre un même problème
(prenant en entrée un tableau de n entiers), on dispose :
o d'un Algo1 qui effectue n2 opérations
o d'un Algo2 qui effectue 2n opérations 23
 1) Intuition
• Avec un processeur 1.8 GHz: 1.8 milliards d'opérations
par seconde, soit 0.5 nanoseconde par opération.
• Si n=32:
• Algo1 effectue n2 = 1024 opérations, soit environ 500
nanosecondes
• Algo2 effectue 2n ≈ 4 milliards d'opérations, soit environ 2
secondes

• Si n=40 (seulement 8 cases de plus!):

• Algo1 effectue n2 = 1600 opérations, soit environ 800
nanosecondes
• Algo2 effectue 2n ≈ 1 000 milliards d'opérations, soit
environ 500 secondes, 8 min!! 24
 1) Intuition
• En résumé: le nombre d'opérations à effectuer au
cours de l'exécution d'un algorithme est un critère
important pour décider si un algorithme est "bon", ou
plutôt efficace.
• On comptera le nombre d'opérations à effectuer en
fonction d'un des éléments de l'entrée.
• Un petite augmentation dans la taille de notre entrée
peut entraîner une grande augmentation du temps de
résolution, même avec les ordinateurs modernes
rapides.

25
 Vocabulaire
• A partir de maintenant, on utilisera souvent
l'expression "un algorithme qui prend en entrée…"
• Cela signifie la même chose que "une fonction qui
prend en argument…."
• Exemple:
Alice a écrit un algorithme qui prend en entrée un
tableau à n cases et qui renvoie le maximum parmi
toutes les cases du tableau.
= Alice a écrit une fonction qui prend en argument un
tableau à n cases et qui renvoie le maximum parmi
toutes les cases d'un tableau. 26
 2) Comparaison asymptotique
●Retour sur l’exemple précédent: Pour résoudre un
problème sur un tableau de n entiers, on dispose :
o d'un Algo1 qui effectue n2 opérations
o d'un Algo2 qui effectue 2n opérations

Comme on l’a vu, Algo1 2

offre de bien meilleurs
temps de calcul lorsque 2
n grandit.
 2) Comparaison asymptotique
Il existe un outil mathématique pour comparer
asymptotiquement deux fonctions :
Notations de Landau : ,,Ω,Θ

En informatique, on s’intéresse à des tailles d’entrées

(entier ) et on veut comparer des complexités
lorsque n grandit ( → + ∞)
On notera  2 = (2 ) par exemple pour dire que  2 est
négligeable devant 2  quand  → + ∞
 2) Comparaison asymptotique
Notation Grand O :   = (  )

Définition : On dit que   = (  ) si pour tout  ≥

1,   ≤  ⋅ () où  est une constante.
Cas particulier :  = 1. Si   ≤ (), alors   =    .

Philosophie : « La fonction  ne croît pas plus vite que

. Elle est au pire proportionnelle à  ».
 2) Comparaison asymptotique
Définition : On dit que   = (  ) si pour tout  ≥
1,   ≤  ⋅ () où  est une constante.

Exemples :
 = (4) ?
5 = (2) ?
2 = () ?
 2) Comparaison asymptotique
Définition : On dit que   = (  ) si pour tout  ≥
1,   ≤  ⋅ () où  est une constante.

Exemples :
 = (4) ? Oui ! Car  ≤ 4 pour tout  ≥ 1
5 = (2) ?
2 = () ?
 2) Comparaison asymptotique
Définition : On dit que   = (  ) si pour tout  ≥
1,   ≤  ⋅ () où  est une constante.

Exemples :
 = (4) ? Oui ! Car  ≤ 4 pour tout  ≥ 1
5 = (2) ? Oui ! Car 5 ≤ 3 ⋅ 2 = 6
2 = () ?
 2) Comparaison asymptotique
Définition : On dit que   = (  ) si pour tout  ≥
1,   ≤  ⋅ () où  est une constante.

Exemples :
 = (4) ? Oui ! Car  ≤ 4 pour tout  ≥ 1
5 = (2) ? Oui ! Car 5 ≤ 3 ⋅ 2 = 6
2 = () ? Non ! Par contradiction, si c’était le cas, il
existerait  tel que  2 ≤  ⋅  pour tout  ≥ 1, ce qui
impliquerait  ≤  pour tout , absurde
 2) Comparaison asymptotique
Exemples :
8 = (1)
500 = ( log  )
1000 = (2 )
2 + 4 = ()
2 + 40 + 351 = ( 2 )
4  + 80 = ( )
! = (  )
 2) Comparaison asymptotique
Notation petit o :   = (  )

()
Définition : On dit que   = (  ) si →0
()

Philosophie : « () est négligeable devant () quand

 devient très grand ».
 2) Comparaison asymptotique
()
Définition : On dit que   = (  ) si →0
()

Exemples :
 = (4) ?
5 = ( 2 ) ?
 = ( log  ) ?
 2) Comparaison asymptotique
()
Définition : On dit que   = (  ) si →0
()

Exemples :
 1
 = (4) ? Non ! Car =
4 4
5 = ( 2 ) ?
 = ( log  ) ?
 2) Comparaison asymptotique
()
Définition : On dit que   = (  ) si →0
()

Exemples :
 1
 = (4) ? Non ! Car =
4 4
2 5 5
5 = ( ) ? Oui ! Car 2 = →0
 

 = ( log  ) ?
 2) Comparaison asymptotique
()
Définition : On dit que   = (  ) si →0
()

Exemples :
 1
 = (4) ? Non ! Car =
4 4
2 5 5
5 = ( ) ? Oui ! Car 2 = →0
 
 1
 = ( log  ) ? Oui ! Car = →0
log  log 
 2) Comparaison asymptotique
Exemples :
8 = ( log  )
500 = ( log  )
1000 = (2 )
33 + 18 = ( 4 )
2 = (3 )
4  + 80 = ( 1.7 )
! = (  )
 2) Comparaison asymptotique
Notation Omega :   = Ω(  )

Définition : On dit que   = Ω(  ) si

  = (  )

Philosophie : « g() ne croît pas plus vite que ()

quand  grandit».
 2) Comparaison asymptotique
Définition : On dit que   = Ω(  ) si   =
(  )

Exemples :
 = Ω(4)
2 = Ω()
 = Ω( log  )
 2) Comparaison asymptotique
Notation Theta :   = Θ(  )

Définition : On dit que   = Θ(  ) si pour tout  ≥

1, 1 ⋅   ≤   ≤ 2 ⋅ ()

Philosophie : « () et () sont proportionnels, leur

croissance est similaire, à une constante près.»
 2) Comparaison asymptotique
Définition : On dit que   = Θ(  ) si pour tout  ≥
1, 1 ⋅   ≤   ≤ 2 ⋅ ()

Exemples :
 = Θ(4) ?
2 = Θ() ?
4 2 + 5 + 10 = Θ( 2 ) ?
 2) Comparaison asymptotique
Définition : On dit que   = Θ(  ) si pour tout  ≥
1, 1 ⋅   ≤   ≤ 2 ⋅ ()

Exemples :
1
 = Θ(4) ? Oui ! Avec 1 = 2 =
4
2 = Θ() ?
4 2 + 5 + 10 = Θ( 2 ) ?
 2) Comparaison asymptotique
Définition : On dit que   = Θ(  ) si pour tout  ≥
1, 1 ⋅   ≤   ≤ 2 ⋅ ()

Exemples :
1
 = Θ(4) ? Oui ! Avec  1 = 2 =
4
2 = Θ() ? Non ! Car on n’a pas  2 ≤ 2 ⋅ 
4 2 + 5 + 10 = Θ( 2 ) ?
 2) Comparaison asymptotique
Définition : On dit que   = Θ(  ) si pour tout  ≥
1, 1 ⋅   ≤   ≤ 2 ⋅ ()

Exemples :
1
 = Θ(4) ? Oui ! Avec  1 = 2 =
4
2 = Θ() ? Non ! Car on n’a pas  2 ≤ 2 ⋅ 
4 2 + 5 + 10 = Θ( 2 ) ? Oui ! Car :
42 ≤ 42 + 5 + 10 ≤ 19 2
 2) Comparaison asymptotique
Grand O: () est inférieure à une  = (4)
  = (  ) constante fois () 5 = (2)
 = ( log  )
petit o: () est négligeable devant 4 = ( 2 )
  = (  ) () 4 = (2 )
30 = ( log  )
Omega:   = (  )  = Ω(4)
  = Ω(  )  = Ω( )
2 = Ω(10 )
Theta: () est 4 = Θ()
  = Θ(  ) asymptotiquement 5 = Θ(2)
proportionnelle à () 3 + 2 = Θ( 3 + 2 )
 2) Comparaison asymptotique
Quelques règles:
• Si   = (  ) alors   = (  )
L’inverse est faux ! Exemple   =   = 

• Si   = Θ(  ) alors   = (  ) et   =

Ω(  ), mais on a pas   = (  )

• Si   = (  ) alors a priori   = (  ) ou

alors   = Θ(  )
Pas valide mathématiquement, mais le plus souvent vrai en algorithmique
 2) Comparaison asymptotique
Quel rapport avec l’algorithmique ?
Pour résoudre un problème sur un tableau de n entiers,
on dispose :
o d'un Algo1 qui effectue () opérations
o d'un Algo2 qui effectue () opérations

Si   = (  ) alors Algo1 bien meilleur que Algo2

Si   = (  ) alors Algo2 pas meilleur que Algo1
Si   = Θ(  ) alors Algo1 et Algo2 sont comparables
2) Comparaison asymptotique
Source Wikipedia :
page
« Comparaison
asymptotique »

Ecart entre
plusieurs fonctions
qui sont toutes
« petit o » entre
elles.