Complexit´e des algorithmes
Un mˆeme probl`eme peut ˆetre r´esolu par plusieurs algorithmes
diff´erents.
Mˆeme s’il est correct, un algorithme peut ˆetre inutile : trop lent, ou
n´ecessite trop d’espace m´emoire.
Exemple : Ensemble de n villes reli´ees par des routes.
Probl`eme : Trouver le parcours le plus court qui traverse toutes les
villes.
Algorithme possible :
– Lister tous les chemins possibles ;
– Pour chaque chemin, v´erifier s’il contient un ´el´ement rouge.
Impossible d’utiliser cet algorithme pour n trop grand.
1
Complexit´e d’un algorithme : temps d’ex´ecution et espace m´emoire
requis.
Comment mesurer l’efficacit´e en temps d’un algorithme ? Temps
d’ex´ecution pas une bonne mesure :
– Environnement de programmation : mˆeme programme ex´ecut´e
sur un Cray ou sur un PC ne prend pas du tout le mˆeme temps.
– Langage de programmation : par exemple, programme compil´e
prend moins de temps qu’un programme interpr´et´e.
– Logique de programmation, d´etails de l’impl´ementation.
Temps d’ex´ecution d´epend de plusieurs facteurs non reli´es `a
l’algorithme.
2
Complexit´e en temps `a priori, d´epend de :
– Taille de l’entr´ee
– Op´erations ´el´ementaires effectu´ees,
Op´eration ´el´ementaire : op´eration dont le temps d’ex´ecution ne
d´epend pas de la taille des op´erandes.
Par exemple, addition de deux entiers. Addition de deux tableaux
pas une op´eration ´el´ementaire.
Calculer, en fonction de la taille n de l’entr´ee :
– Complexit´e en temps dans le meilleur des cas
– Complexit´e en temps dans le pire des cas
– Complexit´e en temps en moyenne
3
Exemple : Recherche du plus grand ´el´ement dans une liste (voir
cours 1, Algorithmique).
– Taille de l’entr´ee : Taille n de la liste
– Op´erations ´el´ementaires : Comparaisons d’entiers deux `a deux,
addition, assignation de valeurs.
Pour une valeur n d’entr´ee, n − 1 passages dans la boucle Tant que
Dans ce cas, meilleur des cas = cas moyen = pire des cas
−→ proportionnel `a n − 1
A chaque passage dans la boucle `
Tant que, 2 comparaisons, 2
assignation, 1 addition −→ 5 op´erations ´el´ementaires.
=⇒ Temps d’ex´ecution : t(n) = 5.n + 2
Tr`es d´ependant de l’impl´ementation. En g´en´eral, les constantes ne
nous int´eressent pas.
4
Complexit´e : Ordre de grandeur par rapport `a la taille de l’entr´ee
t(n) = 60n
2
+ 5n + 1, pour n suffisemment grand, t(n) ∼ n
2
D´efinition : f et g deux fonctions sur N.
– f(n) = O(g(n)) (f(n) est de l’ordre de g(n) au plus) ssi il existe
une constante C1 > 0 telle que : |f(n)| ≤ C1|g(n)|, sauf pour un
nombre fini de valeurs de n.
– f(n) = Ω(g(n)) (f(n) est de l’ordre de g(n) au moins) ssi il existe
une constante C2 > 0 telle que : |f(n)| ≥ C2|g(n)|, sauf pour un
nombe fini de valeurs de n.
– f(n) = Θ(g(n)) (f(n) est de l’ordre de g(n)) ssi f(n) = O(g(n))
et f(n) = Ω(g(n)).
5
Si f(n) = O(g(n)), g croˆıt au moins aussi vite que f.
Exemple : Si f(n) = n et g(n) = 2n
, f(n) = O(g(n)). Mais g croˆıt
beaucoup plus vite que f.
Ici, f(n) 6= Θ(g(n)).
Si f(n) = Θ(g(n)), on peut conclure que f et g croˆıent `a la mˆeme
vitesse, `a par pour un ensemble fini de valeurs de n.
6
Th´eor`eme 1 :
Soit f(n) le polynˆome de degr´e k :
f(n) = ak
n
k
+ ak−1
n
k−1
+ · · · + a1
n + a0
avec ak, ak−1, · · · , a1, a0
des valeurs ≥ 0.
Alors, f(n) = Θ(n
k
)
On montre aussi que :
1. f(n) = ak
n
k
+ ak−1
n
k−1
+ · · · + a1
n + b. log2
(n) = Θ(n
k
)
2. f(n) = 1 + 2 + · · · + n = Θ(n
2
)
3. f(n) = 1k
+ 2k
+ · · · + n
k
= Θ(n
k+1)
4. log2
(n!) = Θ(n log2
n)
5. Pour tout entiers a, b > 1 (logb
(a) > 0), logb
(n) = Θ(loga
(n))
7
M´ethode g´en´erale pour trouver la notation Θ
Algorithme de temps d’ex´ecution t(n) :
1. Remplacer toutes les constantes par 1.
2. Garder le plus grand terme dans la fonction, et supprimer les
autres. Les termes sont ordonn´es du plus petit au plus grand
comme suit :
log n n n log n n2
n
3
n
k
2
n
n!
Par exemple, si t(n) = cn n+1
2
, alors t(n) = O(n
2
). On parle de
complexit´e quadratique.
8
Calcul de complexit´e : boucles lin´eaires
1 Pour i = 1 `a n Faire
2 code ;
3 Fin Pour
Nombre d’it´erations directement proportionnel au facteur de
boucle, et donc t(n) = C.n = Θ(n).
1 i = 1 ;
2 Tant que 1 ≤ n Faire
3 code ;
4 i = i + 2 ;
5 Fin Tant que
Nombre d’it´erations : n/2. Donc T(n) = C. n
2
= Θ(n).
9
Boucles logarithmiques
1 i = 1 ;
2 Tant que i ≤ n Faire
3 code ;
4 i = i × 2 ;
5 Fin Tant que
It´eration Valeur de i It´eration Valeur de i
1 1 6 32
2 2 7 64
3 4 8 128
4 8 9 256
5 16 10 512
(sortie) 1024
10
Boucle s’arrˆete d´es que i − 1 ≥ log2
n ⇒ i ≥ log2
n + 1
t(n) = cdlog2
ne = Θ(log2
(n))
Pour les mˆemes raisons, l’algorithme suivant a un temps
logarithmique.
1. i = 1000 ;
2. Tant que i ≥ 1 Faire
3. code ;
4. i = i/2 ;
5. Fin Tant que
11
Boucles imbriqu´ees
1 Pour i = 1 `a n Faire
2 j = 1 ;
3 Tant que j ≤ n Faire
4 j = j × 2 ;
5 Fin Tant que
6 Fin Pour
Boucle interne → dlog2
ne it´erations,
Boucle externe → n it´erations
⇒ t(n) = cndlog2
ne = Θ(n. log2
n)
12
1 Pour i = 1 `a n Faire
2 Pour j = 1 `a i Faire
3 j = j + 1 ;
4 Fin Pour
5 Fin Pour
Nombre de fois que la boucle interne est ex´ecut´ee d´epend de
l’indice de la boucle externe.
Boucle interne effectu´ee 1 + 2 + 3 + · · · + (n − 1) + n =
n(n+1)
2
fois.
⇒ t(n) = Θ(n
2
)
13
1 j = n ;
2 Tant que j ≥ 1 Faire
3 Pour i = 1 `a j Faire ;
4 x = x+1 ;
5 Fin Pour
6 j = bj/2c ;
7 Fin Tant que
Si k est le nombre de fois que la boucle Tant que est ex´ecut´ee,
l’instruction 4 est ex´ecut´ee au plus :
n +
n
2
+
n
4
+ · · · +
n
2
k−1
Somme g´eom´etrique : a + a.r + a.r2
+ · · · + arn
=
a(r
n+1
−1)
r−1
−→
n(1− 1
2
k
)
1− 1
2
≤ 2n pour n ≥ 1
⇒ t(n) = O(n) = Θ(n)
14
Recherche d’un ´el´ement dans une liste
Entr´ee : s1, s2, · · · sn, n, et elt;
Sortie : L’indice de elt s’il est trouv´e, et 0 sinon
Proc´edure recherche-element (s, n, elt)
i = 1 ;
Tant que (i ≤ n) et (elt 6= si
) Faire
i = i + 1 ;
Fin Tant que
Si i = n + 1
Retourne (0)
Retourne (i)
Fin recherche-element
Meilleur des cas : s1 = elt ⇒ Θ(1)
Pire des cas : elt n’est pas dans la liste ⇒ Θ(n)
En moyenne : La boucle est parcourue n/2 fois ⇒ Θ(n)
15
Mesures standard d’efficacit´e
n = 10000. Estimation du temps effectu´ee en supposant qu’il y a 10
instructions dans une boucle, et que chaque instruction est ex´ecut´ee
en une microseconde.
Efficacit´e Notation Θ It´erations Temps estim´e
Logarithmique Θ(log2
n) 14 Microsecondes
Lin´eaire Θ(n) 10 000 0.1 secondes
Θ(nlog2n) 140 000 2 secondes
Quadratique Θ(n
2
) 10 0002
15 − 20 minutes
Polynˆomiale Θ(n
k) 10 000k
Heures
Exponentielle Θ(2n) 2
10000 Insoluble
Factorielle Θ(n!) 10 000! Insoluble
16