Chapitre I
Complexité algorithmique
1. Introduction à la complexité
Le premier à avoir systématisé le fait de calculer la complexité d’un algorithme est Donald Knuth (né
en 1938) dans sa série d’ouvrage "The Art of Computer Programming".
1.1. Problématique
Il existe une multitude de solutions (d'algorithmes) à coder pour résoudre un problème. La difficulté
réside dans le fait de trouver la solution la plus efficace. L’efficacité d’un algorithme dépend de
certaines ressources, telles que :
- la vitesse du processeur
- la taille et la vitesse de transfert de la mémoire dont il dispose
- la taille et vitesse de transfert du disque
- la vitesse de transfert du réseau
- etc.
Dans ce qui suit, nous nous concentrons sur le temps indépendamment de la nature ou des capacités
des ressources.
1.2. Définition
Le calcul de complexité consiste à examiner différentes façons de comparer des algorithmes et
d'exprimer la durée d'exécution d'un algorithme en tant que fonction de la taille des données.
Supposons que nous ayons deux algorithmes ou plus conçus pour résoudre le même problème. Il y a
deux façons principales de comparer leurs temps d'exécution :
Analyse comparative (benchmarking) : coder et exécuter les deux programmes avec les mêmes
entrées (sous-ensemble fini) et mesurer leurs temps d'exécution.
Analyse prédictive : développer des formules prédictives de leurs temps d'exécution. C’est cette
solution que nous étudions.
On veut donc évaluer l’efficacité d’une méthode M et la comparer avec une autre méthode M′
indépendamment de l’environnement (machine, système, compilateur, …). Ce type de comparaison
est primordial, car pour des données volumineuses, la différence entre les durées d'exécution de
deux algorithmes ayant la même finalité peut être de l'ordre de plusieurs jours.
2. Calcul de complexité
2.1. Notation
Pour la mesure de la complexité, on s’intéresse à l’évaluation du nombre d’opérations élémentaires
en fonction de la taille des données. On supposera que les algorithmes n'ont qu'une donnée, dont la
taille est un entier naturel. La complexité en temps d’un algorithme sera donc une fonction de ℕ
dans ℝ + . Nous la noterons T (pour Time). En général, on note :
n : taille des données,
T(n) : nombre d’opérations élémentaires ou complexité
1
Matière : ASD 3 Chapitre 1 Complexité algorithmique
On pourra donc estimer que le temps d'exécution d’un algorithme est proportionnel au nombre
d’opérations élémentaires qui dépendra de son coté des données. Plus ces données seront
volumineuses, plus il faudra d'opérations élémentaires pour les traiter. Par exemple, pour un
algorithme de tri, cette taille sera le nombre de valeurs à trier.
On émet l'hypothèse que toutes les opérations élémentaires sont à égalité de coût. En pratique ce
n'est pas tout à fait exact, mais cette approximation est cependant raisonnable.
2.2. Dépendance de la taille des entrées
Le temps d'exécution d'un algorithme est la somme des parties
fixe : indépendante des paramètres
variable : dépendante des paramètres
Exemple : la durée d'exécution de l'algorithme suivant
Paramètres : entier positif n
int i, sum = 0;
for (i = 1; i<=n; i++)
{ sum = sum + i; }
return sum;
est le temps nécessaire pour initialiser la somme et la retourner (partie fixe) et le temps à exécuter le
corps de la boucle, qui dépendra de la valeur de n (partie variable).
Par exemple, TailleDePile dans l’implémentation d’une pile renvoie toujours le nombre d’éléments
actuellement dans la pile ou indique que la pile est vide. On dit que TailleDePile prend un temps
constant. Par contre, dans l’algorithme Tri à bulle (voir prochains chapitres), le nombre d’éléments
du tableau n, détermine le nombre d'opérations effectuées par l'algorithme. Ce paramètre est
appelé taille du problème.
2.3. Pires, meilleurs et moyens cas (Worst, Best and Average Cases)
Il existe cependant une difficulté. Certains algorithmes auront des temps d'exécution différents
même pour deux instances de données de même taille. Par exemple, il est probable qu’un
algorithme de tri fera moins de travail pour les instances qui sont déjà triées. Ainsi, la complexité
dépend aussi de la donnée en elle-même et pas seulement de sa taille.
Par exemple, pour effectuer une recherche séquentielle d’un élément dans une liste non triée, il est
possible de s’arrêter dès le début si le premier élément est le bon. Mais il est également possible
d’être amené à parcourir la liste en entier si l’élément cherché est en dernière position, ou même n'y
figure pas. Le nombre d'opération élémentaires effectuées dépend donc non seulement de la taille
de la liste, mais également de la répartition de ses valeurs.
Donc, comment pouvons-nous trouver une fonction T(n) ?
On distingue trois formes de complexité en temps
Complexité dans le meilleur des cas : correspond par exemple à la recherche d'un élément
situé à la première position d'une liste, ou encore au tri d'une liste déjà triée.
Complexité dans le pire des cas : c'est l’exemple de la recherche d'un élément dans une liste
alors qu'il n'y figure pas, ou encore au tri par ordre croissant d'une liste triée par ordre
décroissant.
2
Matière : ASD 3 Chapitre 1 Complexité algorithmique
Complexité en moyenne : les données sont réparties selon une certaine loi de probabilités.
En règle générale, nous nous intéressons au pire des cas : quel est le nombre maximal d’opérations
pouvant être effectuées pour une taille de problème donnée.
Par exemple, pour insérer un élément dans un tableau, nous devons déplacer l'élément en cours et
tous les éléments qui viennent après dans le tableau. Dans le pire des cas, insérer au début du
tableau nécessite que tous les éléments doivent être déplacés. Par conséquent, dans le pire des cas,
le temps d'insertion est proportionnel au nombre d'éléments dans le tableau.
2.4. Evaluation de T(n)
L’évaluation de T(n) consiste alors à déterminer le temps requis pour l’exécution d’un algorithme. Le
tableau suivant présent des exemples d'opérations de base :
Opération Forme T(n)
Opérations arithmétiques a + b, c * d, x – y, … Constante
Affectation Variable = Expression Constante
Test Expression R Expression Constante
R = ‘==’, ‘<’, ‘>’, …
Séquence Traitement1 T1(n) T1(n) + T2(n)
Traitement2 T2(n)
Branchement si < condition > alors max (T1(n), T2(n))
Traitement1 T1(n)
sinon
Traitement2 T2(n)
Boucle tant que <condition> faire ∑𝑘𝑖=1 𝑇𝑖(𝑛) avec Ti(n) : coût de
Traitement Ti(n) la ième itération
fin tant que
Exemples :
1. La fonction suivante convertit un nombre de secondes en heures, minutes, secondes :
conversion(int n):
h = n / 3600
m = (n - 3600*h) / 60
s = n % 60
On peut dénombrer cinq opérations arithmétiques et trois affectations. On a donc T(n) = 8.
2. La fonction suivante calcule (-1)n sans effectuer de produit mais en utilisant un test avec une
alternative :
puissanceMoinsUn(int n):
if (n%2==0)
res = 1 ;
else:
res = -1 ;
3
Matière : ASD 3 Chapitre 1 Complexité algorithmique
Le test de la condition comporte une opération arithmétique et une comparaison. Chaque alternative
possède une affectation, ainsi le maximum des coûts des différentes alternatives est de un. On a
donc T(n) = 3.
3. Cette fonction calcule la somme des n premiers entiers :
sommeEntiers(int n)
somme = 0;
for (i=1; i<=n, i++)
somme += i ;
Ici chaque itération a le même nombre d’opérations, à savoir cinq : deux affections (i et somme),
deux additions (i et somme) et une comparaison. On a d'autre part une affectation, lors de
l'initialisation de la variable somme. Ainsi T(n) = 5n + 2.
4. Cette fonction utilise la formule de calcul d’une suite arithmétique :
sommeEntiersBis(int n)
somme = n*(n+1)/2;
Cet algorithme ne comporte pas de structures de contrôle, il est juste constitué de trois opérations
arithmétiques et une affectation. On a donc T(n) = 4.
Les deux derniers algorithmes nous offrent un exemple de comparaison d'efficacité puisqu'ils
répondent tous deux à la même question. La conclusion est ici évidente, il vaut mieux utiliser le
second.
5. La fonction suivante recherche un élément x dans la liste l. Si x appartient à l, elle retourne
l'indice de la première occurrence de x dans l, sinon elle retourne -1.
recherche(int[] l, int n; int x)
for (i=0; i<n, i++)
if (l[i]==x)
return i;
return -1;
Ici la complexité sera fonction de la longueur de la liste, n. Dans le pire des cas l'élément recherché
n'appartient pas à la liste, et il faut la parcourir en entier pour arriver à cette conclusion, c'est-à-dire
effectuer n itérations. De plus, chaque itération comporte le même nombre d'opérations
élémentaires, à savoir une affectation, une addition et deux comparaisons. On a donc T(n) = 4 n + 2.
2.5. Notation O
Remarquons que donner un résultat précis de la complexité devient vite difficile et inutile. Comment
par exemple ne pas oublier une opération élémentaire dans un algorithme de quelques centaines de
lignes ? D'autre part, que la complexité d'un algorithme soit égale à 4 n + 2 ou 3 n + 5 ne change pas
fondamentalement sa performance. On va donc plutôt s’intéresser à une complexité asymptotique,
qui sera une approximation du nombre d’opérations élémentaires sans perdre en pertinence.
La notation Grand O (Big O en anglais, avec une lettre majuscule O, pas un zéro), également appelée
symbole de Landau, est un symbolisme utilisé dans la théorie de la complexité pour décrire le
4
Matière : ASD 3 Chapitre 1 Complexité algorithmique
comportement asymptotique des fonctions. La lettre O est utilisée parce que le taux de croissance
d’une fonction s'appelle également son ordre.
Définition
Une fonction f(n) est égale à O(g(n)) s’il existe des constantes c > 0 et n0 > 0 telle que pour tout n > n0
f(n) ≤ c g(n)
Intuitivement, cela signifie que f ne croît pas plus rapidement que g, ou encore qu'à partir d'un
certain rang, la fonction f est majorée par une constante fois la fonction g (domination de f par g).
Ce qui signifie que lorsque n tend vers l'infini (n devient très grand en informatique), le rapport
f(n)/g(n) reste borné.
Par exemple, lorsqu’on analyse un algorithme, on peut trouver que le temps (ou le nombre d’étapes)
qu’il faut pour résoudre un problème de taille n est donné par T(n) = 4 n2 - 2 n + 2.
Si nous ignorons les constantes et les conditions de croissance plus lente (2 n), nous pourrions dire
"T(n) se développe à l'ordre de n2 "et écrire : T(n) = O(n2). Nous pouvons montrer que T(n) = O(n2) en
choisissant c = 4 et n0 = 3.
En effet, pour toutes les valeurs de n supérieures à 3 : 4 * n2 – 2 * n + 5 <= 4 * n2
En pratique, nous voulons déterminer le plus petit f(n) - la limite inférieure de la complexité réelle.
Exemples :
O(cn2) = O(n2)
O(c1n2 +c2n) = O(n2) car pour n ≥ 1 c1n2 +c2n ≤ (c1 +c2)n2
Dans un test, si le bloc 1 prend O(1) et que le bloc 2 prend O(n), l'instruction if-then-else
serait O(n).
Supposons une boucle for qui s'exécute n fois. La séquence d'instructions s'exécute
également n fois. Si nous supposons que les instructions sont O(1), le temps total de la
boucle est n * O(1), qui est O(n) global.
Une fonction de complexité O(n) appelée dans une boucle qui s’exécute k fois, aura comme
complexité O(n2).
2.6. Efficacité d’un algorithme
Quand peut-on dire qu’un algorithme est efficace ?
5
Matière : ASD 3 Chapitre 1 Complexité algorithmique
Une complexité exponentielle O(cn) est presque toujours excessive. Par exemple si c = 2 et n = 100
(taille modeste), on a 2100 = 1030. Si chaque opération prend un nanoseconde, l’exécution prendra de
l’ordre de 3 × 1011 siècles ! le temps de calcul est clairement excessif.
La liste ci-dessous est utile en raison du fait suivant : si une fonction f(n) est une somme de fonctions,
dont l’une croît plus vite que les autres, celle qui croît le plus vite détermine l'ordre de f(n).
Notation Nom
O(1) Constante
O(log(n)) Logarithmique
O((log(n))c) Poly logarithmique
O(n) Linéaire
O(n2) Quadratique
O(nc) Polynomial
O(cn) Exponentiel
Exemple : si f(n) = 10 log(n) + 5 (log(n))3 + 7n + 3n2 + 6n3, alors f(n) = O(n3).
