MP1 Lycée Janson de Sailly Complexité

Figure 1 Algorithme vu comme une boîte possédant une entrée et

Chapitre de révision : la complexité une sortie. C’est une séquence d’étapes de calcul qui transforment
l’entrée en sortie.

On appelle taille de l’entrée la "grosseur" caractéristique de l’en-

Table des matières trée. C’est une notion un peu subjective, qui dépend surtout du type
de calculs que fait l’algorithme. En gros, le nombre d’étapes de l’al-
1 Complexité temporelle des algorithmes 1
gorithme dépend directement de la taille de l’entrée :
1) Quelques définitions . . . . . . . . . . . . . . . . . . . 1
2) Complexité temporelle d’un algorithme . . . . . . . . . 1 • Dans le cas de l’algorithme FACTORIELLE, la taille de l’entrée
3) Notation O . . . . . . . . . . . . . . . . . . . . . . . . 4 est l’entier n lui même. Plus n est grand, plus le nombre d’étapes
4) Analyse de la complexité temporelle . . . . . . . . . . 5 pour aboutir au résultat n! est important.
• Dans le cas d’un algorithme de TRI d’un tableau T[0...n − 1],
la taille de l’entrée est le nombre d’éléments à trier, c’est à dire
n.
1 Complexité temporelle des algorithmes
1) Quelques définitions 2) Complexité temporelle d’un algorithme
Cette notion est abordée dans le programme de MPSI. Lorsqu’on
Un algorithme est une procédure de calcul bien définie qui prend
écrit un algorithme ou une fonction, il est important d’évaluer le
en entrée une valeur, ou un ensemble de valeurs, pour produire en
temps qu’il prendra pour produire la sortie : on appelle cela sa
sortie d’autres valeurs ou ensemble de valeurs. Un algorithme est
complexité temporelle. Cette complexité temporelle est calculée
donc une séquence d’étapes de calcul qui transforment l’entrée en
en sommant les coûts temporels 1 de chaque étape, ce qui n’est rien
sortie.
d’autre que la durée de chaque étape.
En voici deux exemples : Exemple 1

Prenons l’exemple de FACTORIELLE(n) dans l’approche itérative.

!
entrée sortie entrée sortie Notons T(n) son temps d’exécution pour une entrée égale à n. Chaque
algo. algo.
FACTORIELLE TRI 1. On préfère parler de coût temporel plutôt que de durée car on va voir plus
entier n n! Tableau Tableau trié tard qu’on peut définir d’autres types de coûts comme par exemple la taille de
T[0…n-1] T2[0…n-1] la mémoire de l’ordinateur nécessitée par une étape, ou encore le coût en opéra-
(a) (b) tions arithmétiques {+, -, * et / }, défini comme étant le nombre d’opérations
arithmétiques nécessaires à chaque étape.

1
MP1 Lycée Janson de Sailly Complexité

ligne Li d’instruction a un coût temporel (durée) ci et elle est Exemple 2 : (remarque 2 )

executée une ou plusieurs fois : Soit n > 1 un entier naturel. Étudions une fonction basée sur un
algorithme qui calcule l’entier p vérifiant : 2p 6 n < 2p+1 .
FACTORIELLE(n) Coût temporel Nbre de fois
1 if n == 0 or n == 1 : c1 1 précondition : n > 1
2 return n c2 1
fonction PUISS2(n) : Coût temporel Nbre de fois
3 else : 0 0
1 p = -1 c1 1
4 fact = 1 c4 1
2 e=1 c2 1
5 for i in range(2,n) : c5 n−1
3 while e <= n : c3 N
6 fact = fact * i c6 n−1
4 p=p+1 c4 N
7 return fact c7 1
5 e = 2*e c5 N
Remarque : 6 return p c6 1
L’instruction else ligne 3 ne coûte rien car elle n’est en réa-
lité jamais exécutée. Le processeur évalue la vérité de l’expression Évaluons le nombre de fois N que l’algorithme parcourt la boucle
n == 0 or n == 1 à la ligne 1. Si elle est vraie (True) il passe à while. Soit i le compteur de boucle ; avant l’entrée dans la boucle,
l’instruction de la ligne 2. Si elle est fausse (False) il passe directe- i = 0 et :
ment à l’instruction de la ligne 4. • À la fin de la première boucle : i = 1 et e(i) = 21
• À la fin de la seconde boucle : i = 2 et e(i) = 22
• T(0) = T(1) = c1 + c2 . • ...
• Pour n > 1, T(n) = c1 + c4 + (n − 1) × c5 + (n − 1) × c6 + • À la fin de la N ième boucle i = N et e(i) = 2N avec
c7 . En regroupant les termes, on obtient :
2N −1 6 n < 2N
T(n) = (c5 + c6 ) × n + (c1 + c4 − c6 + c7 )

donc de la forme :

T(n) = a × n + b pour n > 1

où a et b sont deux constantes.

2. On peut avoir une approche plus brutale avec les coûts temporels en conve-
nant qu’ils sont tous égaux (ci = c). Dans ce cas, le plus simple est de prendre
c = 1, en convenant que ce " 1 " représente une unité de temps-machine, cette
unité de temps pouvant valoir 1 µs, 1 ns par exemple (cela dépend de la machine
utilisée).

2
MP1 Lycée Janson de Sailly Complexité

Un outil indispensable : le logarithme en base 2 Exemple 3 :

Le logarithme en base 2, noté lg est défini par :
Prenons un dernier exemple avec la fonction FACTORIELLE(n)
y = lg(x) ⇐⇒ x = 2y dans l’approche récursive :

On a immédiatement les propriétés suivantes (qui sont les propriétés FACTORIELLE(n) Coût temporel Nbre de fois
classiques des logarithmes) : 1 if n == 0 or n == 1 : c1 1
2 return n c2 1
• ln(x) = ln(2) × lg(x). On remarque donc que lg(x) n’est défini 3 else : 0 0
que sur R∗+ et que c’est une fonction croissante a . 4 x = n * FACTORIELLE(n − 1) 0
c4 + T(n − 1) 1
• ∀ (x, y) ∈ R∗+ × R∗+ , lg(xy) = lg(x) + lg(y). 5 return x c5 1
• ∀ a ∈ R, ∀ x ∈ R∗+ lg(xa ) = a lg(x).
• ∀ a ∈ R, a = lg(2a ). En particulier : lg(2) = 1 Remarque :
a. ln(x) représente le logarithme népérien de x.
Le coût temporel de la ligne 4 correspond au coût de
Il vient donc : FACTORIELLE(n − 1), c’est à dire T(n − 1) plus le coût de la multi-
plication par n et de l’affectation à la variable x que nous avons noté
2N −1 6 n < 2N ⇐⇒ N − 1 6 lg(n) < N c04 .

On constate facilement que : On a donc :

noté
• T(0) = T(1) = c1 + c2 = b.
T (n) = c1 + c2 + c6 + N × (c3 + c4 + c5 ) • Si n > 1, T(n) = c1 + c’4 + T(n − 1) + c5 . En regroupant les
termes, nous obtenons : T(n) = T(n − 1) + c1 + c’4 + c5 , donc
et comme N 6 lg(n) + 1 il vient : de la forme :
T(n) 6 c1 + c2 + c6 + c3 + c4 + c5 + lg(n) × (c3 + c4 + c5 ) T(n) = T(n − 1) + a

donc, de façon générale : avec a = c1 + c’4 + c5 .

T(n) est donc défini par une récurrence : il s’agit d’une suite
T (n) 6 a × lg(n) + b
arithmétique de raison c. On obtient finalement : T(n) = a × n +
où a et b sont deux constantes. On vera plus loin pourquoi il est T(0). En conclusion, comme pour l’approche itérative, T(n) est une
important de majorer T(n). fonction affine de n. On a donc :

T(n) = a × n + b

3
MP1 Lycée Janson de Sailly Complexité

3) Notation O Règles de calcul avec O

f , g et h étant trois applications de N dans R+ , on a :
D’une façon générale, n représente la taille de l’entrée et T(n) le 1. f = O(f )
temps que met l’algorithme (ou la fonction) pour obtenir la sortie 2. Si f = O(g) et g = O(h), alors f = O(h).
avec une entrée de taille n.
C’est la propriété de transitivité de la notation O.
h(n)
Ce qui importe le plus au programmeur est le comportement 3. Si f = O(g + h) et que lim = 0, alors f = O(g)
n→+∞ g(n)
asymptotique de T(n) lorsque n est grand. En effet, ce sont les
grandes valeurs de la taille de l’entrée qui qui auront l’effet le plus Cela signifie que, dans une somme de deux termes, seul le terme
critique sur le temps de calcul (très énervant pour l’utilisateur qui prépondérant est important.
doit patienter parfois assez longtemps...). 4. Si a ∈ R+ (constante positive) et si f = O(ag) alors f = O(g)
Une constante multiplicative peut être omise.
Pour rendre cela opérationnel et efficace, il est nécessaire d’intro-
duire les définitions et notations suivantes : Preuves :
Définition et notation O 1. C’est évident : il suffit de prendre N = 0 et c = 1. On a alors
Soient f et g deux applications de N −→ R+ , à valeurs réelles po- ∀ n > 0, f (n) 6 f (n).
sitives. On dit que f = O(g) (prononcer "f est grand O de g") si et 2. Si f = O(g) alors il existe N1 ∈ N et c1 ∈ R+ tels que :
seulement si :
∀ n > N1 , f (n) 6 c1 × g(n)
∃ N ∈ N et ∃ c ∈ R+ (constante) t.q. ∀ n > N, f (n) 6 c × g(n)
De même si g = O(h) alors il existe N2 ∈ N et c2 ∈ R+ tels
On dit que f est dominée par g.
que :
∀ n > N2 , g(n) 6 c2 × h(n)
Posons alors N = max(N1 , N2 ). On en déduit que :

∀ n > N, f (n) 6 c1 × g(n) 6 c1 c2 × h(n)

Il suffit alors de prendre c = c1 c2 et on a donc bien f = O(h).

3. Comme f = O(g + h), il existe N1 ∈ N et c ∈ R+ tels que :

∀ n > N1 , f (n) 6 c1 × (g(n) + h(n))

4
MP1 Lycée Janson de Sailly Complexité

h(n) 4) Analyse de la complexité temporelle

De plus comme lim = 0, il existe N2 ∈ N tel que :
n→+∞ g(n)
La notation O est très commode pour classer les algorithmes par
h(n) ! complexité temporelle croissante.
∀ n > N2 , 6 1 ⇐⇒ h(n) 6 g(n)
g(n)
Efficacité temporelle
Posons alors N = max(N1 , N2 ). On en déduit que : croissante

∀ n > N, f (n) 6 2c1 × g(n)

O(1) O(lg n) O(n) O(n lg n) O(n2) O
et il suffit de prendre c = 2c1 pour montrer que f = O(g).
4. Si f = O(ag) avec a ∈ R+ , il existe N ∈ N et c1 ∈ R+ tels que :

∀ n > N, f (n) 6 c1 × ag(n) = (ac1 ) × g(n) Complexité temporelle

croissante
On prend donc c = ac1 et la propriété est démontrée : f = O(g).

Application : analysons la complexité temporelle des trois exemples Figure 2 Classement des algorithmes en fonction de leur complexité
précédents : temporelle.

Exemple 1 : T(n) = a × n + b si n > 2. On a donc T = O(an + b) Remarque :

(règle 1) = O(an) (règle 3) = O(n) (règle 4), donc :
Lorsque la complexité temporelle est en O(1) cela signifie que, si n
T(n) = O(n) est ”assez grand”, il existe une constante c telle que : T(n) 6 c. On
dit que l’algorithme s’exécute à temps constant.
Exemple 2 : T(n) 6 a × lg(n) + b pour n ∈ N∗ . On prend N = 1
et c = 1 et on a donc T = O(a lg(n) + b) = O(a lg(n)) (règle 3) =
O(lg(n)) (règle 4), donc :

T(n) = O(lg(n))

Exemple 3 : c’est la même chose que l’exemple 1 et donc

T(n) = O(n)