Chapitre 8 : Complexité

On veut évaluer le coût informatique de l’éxecution d’un programme. Pour cela, il faut avoir défini quelles sont les res-
sources qui ont un coût.
Les ressources ayant un coût les plus généralement utilisées sont :
• l’espace mémoire (on parle alors de complexité spatiale)
• le temps (on parle alors de complexité temporelle).
Pour l’étude de la complexité temporelle, on ne raisonne pas en termes de durée mais en nombre d’opérations élémentaires.
En effet, la durée d’éxecution d’un programme dépend des performances de l’ordinateur ce qui n’est pas le cas du nombre
d’opérations élémentaires qui ne dépend que du programme écrit.
De plus, on ne s’intéressera pas au nombre exact d’opérations élémentaires effectuées mais uniquement à leur ordre de
grandeur.

I Généralités
1.1 Opérations élémentaires
La première étape consiste à préciser quels sont les opérations élémentaires (i.e celles considérées comme ayant un coût
constant indépendamment de leurs paramètres).
On considérera en général comme opérations élémentaires les opérations suivantes :
• les opérations arithmétiques (addition +, soustraction -, division /, multiplication *, division entière //, reste % ...)
• les affectations
• les comparaisons avec des données qui ne sont pas des séquences

Le nombre d’opérations élémentaires requis par un algorithme doit être exprimé en fonction de « la taille »des données.
Cette notion dépend des paramètres d’entrée et donc du problème étudié. En général, on prend :
• la longueur d’une liste, si l’algorithme prend une liste en paramètre ;
• l’entier n, lorsque le problème dépend d’un entier naturel n ;
• ...
En notant C n le nombre d’opérations élémentaires d’un algorithme pour une donnée de taille n, on peut donc voir ce nombre
d’opérations élémentaires comme une suite.

1.2 Outils mathématiques

Définition : Soient (u n ) et (v n ) deux suites réelles telles que (v n ) ne s’annule pas à partir ¶ rang n 0 .
µ d’un
un
On dit que (u n ) est dominée par (v n ) et on note u n = O(v n ) si et seulement si le quotient est borné
v n n≥n0
¯ ¯
¯ un ¯
si et seulement si : ∃M ∈ R+ , ∀n ≥ n 0 , ¯¯ ¯¯ ≤ M
vn
si et seulement si : ∃M ∈ R+ , ∀n ≥ n 0 , |u n | ≤ M |v n |
Exemple : n 2 + 10n = O(n 2 ), 10000n 4 − 8n 3 = O(n 4 ).

1.3 Classes de complexité

On va évaluer les algorithmes en étudiant leur complexité. Afin de pouvoir les comparer, nous allons les classer par ordre
croissant de complexité :
On parle de :
• complexité constante si le nombre d’opérations élémentaires est un O(1)
• complexité logarithmique si le nombre d’opérations élémentaires est un O(ln n)
• complexité linéaire si le nombre d’opérations élémentaires est un O(n)
• complexité quasi-linéaire si le nombre d’opérations élémentaires est un O(n ln n)
• complexité quadratique si le nombre d’opérations élémentaires est un O(n2 )
• complexité polynomiale si le nombre d’opérations élémentaires est un O(nk )
• complexité exponentielle si le nombre d’opérations élémentaires est un O(an ), avec a > 1

Afin de prendre conscience des différences d’échelles considérables entre ces ordres de grandeur, considérons un pro-
cesseur effectuant 109 opérations par seconde et étudions le temps d’exécution d’un algorithme en fonction de la taille n des
données (10,102 , ...) et du nombre C n d’opérations élémentaires requis par l’algorithme (n, ln n, n 2 ...) :

1
 XX
Cn
n2 n3 2n
XXX
X l n(n) n nl n(n) n!
taille n de l’entrée XXX
X
10 2 ns 10 ns 23 ns 100 ns 1 µs 1 µs 3.6 ms
102 5 ns 100 ns 461 ns 10 µs 1 ms 4.1013 années 3.10141 années
103 7 ns 1 µs 7 µs 1 ms 1s 3.10284 années
104 9 ns 10 µs 92 µs 100 ms 17 mi n
106 14 ns 1 ms 14 ms 17 mi n 32 années
108 18 ns 100 ms 2s 116 jours 3.107 années
Temps nécessaire à l’exécution d’un algorithme en fonction de sa complexité

1.4 Complexité dans le meilleur cas et complexité dans le pire cas

Lors du calcul de la complexité temporelle, on ne prendra pas en compte tous les cas possibles. On pourra calculer deux
complexité temporelles différentes :
• la complexité dans le pire cas
• la complexité dans le meilleur cas.
Lorsque ce n’est pas précisé, la complexité désignera la complexité dans le pire cas. En effet, la complexité dans le pire cas
est la complexité la plus importante car lorsqu’on applique un programme, on ne sait pas, en général, dans quel cas on se
trouve.

II Complexité spatiale
La complexité spatiale a pour objectif d’estimer l’espace mémoire nécessaire à l’exécution d’un algorithme. En effet, lors
de l’appel d’une fonction, des variables locales sont créées et effacées à la fin de l’exécution de la fonction. Mais, malgré tout,
il faut s’assurer que l’espace mémoire utilisé lors de l’appel de la fonction n’est pas trop grand. Pour estimer cette complexité,
on convient qu’une valeur de type int, float, bool a une complexité spatiale en O(1), alors que par exemple une liste d’élé-
ments de longueur n de type simple a une complexité spatiale en O(n) où n désigne la longueur de la liste.

Avec le développement des techniques de stockage ( mémoire vive ...), la complexité spatiale est en générale moins limi-
tative à l’utilisation d’un algorithme que la complexité temporelle.
Exemple 1 :
1 def somme(n) :
2 s=0
3 for i in range(n+1) :
4 s+=i
5 return s
Les variables stockées sont : les entiers n et s. Comme 2 = 0(1), la complexité spatiale est : O(1).

Exemple 2 :
1 def max(l) :
2 m=l[0]
3 imax=0
4 for i in range(len(l)) :
5 if m<l[i] :
6 m=l[i]
7 imax=i
8 return [imax,m]
Les variables stockées sont : une liste l de taille notée n, un flottant m et un entier i max. Comme n + 2 = 0(n), la com-
plexité spatiale est : O(n).

2
III Complexité des structures de contrôle usuelles
Dans toute la suite, les complexités considérées seront des complexités temporelles.
On notera C (opération) la complexité d’une opération :

3.1 Branchement conditionnel

Supposons que l’on ait un programme de la forme :

if condition :
instruction1
else :
instruction2

La complexité de ce programme est :

O(C (condition)) + max (O(C (instruction1)),O(C (instruction2)))

Remarque : Le coût de la condition est toujours pris en compte car on la teste dans tous les cas. On ne sait pas, une
fois la condition testée, quelle instruction va être effectuée, c’est pourquoi, on prend en compte le maximum du coût des
instructions.

3.2 Boucles for

Supposons que l’on ait un programme de la forme :

for k in range(a,b) :
instruction

La complexité de ce programme est :

b−1
X
O(C (instruction))
k=a

et dans le cas particulier où le coût de l’instruction ne dépend pas de k :

(b − a)O(C (instruction))

3.3 Boucles while

Supposons que l’on ait un programme de la forme :

while condition :
instruction

La complexité de ce programme est :

(nombre d’itérations) × (O(C (condition)) + O(C (instruction)))

où on suppose ici que le coût de la condition et le coût de l’instruction sont constants.

Remarque : La difficulté est d’estimer le nombre d’itérations. En pratique, on cherche uniquement un majorant du
nombre d’itérations.

3.4 Exemples
Exemple 1 :
1 def somme(n) :
2 s=0
3 for i in range(n+1) :
4 s+=i
5 return s
On effectue :
• 1 affectation,
• une boucle for de longueur n + 1 avec, à chaque itération, 1 addition et 1 affectation,
• 1 renvoi.

3
Le nombre total d’opérations est donc : 1 + 2(n + 1) + 1 = O(n).
La complexité est donc O(n), c’est-à-dire linéaire.

Exemple 2 :
1 def max(l) :
2 m=l[0]
3 imax=0
4 for i in range(len(l)) :
5 if m<l[i] :
6 m=l[i]
7 imax=i
8 return [imax,m]
On pose : n = l en(l ). On effectue :
• 2 affectations,
• une boucle for de longueur n avec, à chaque itération, 1 comparaison et au plus 2 affectations,
• 1 renvoi.
Le nombre total d’opérations est donc : 2 + 3n + 1 = O(n).
La complexité est donc O(n), c’est-à-dire linéaire.

Exemple 3 :
1 def recherche(l,x) :
2 i=0
3 while i<len(l) and l[i] !=x :
4 i+=1
5 if i==len(l) :
6 return False
7 else :
8 return True
On pose : n = l en(l ). On effectue :
• 1 affectation,
• une boucle while de longueur au plus n avec, à chaque itération, 2 comparaisons et 1 addition,
• 1 comparaison avec, dans tous les cas, 1 renvoi.
Le nombre total d’opérations est donc : 1 + 3n + 2 = O(n).
La complexité est donc O(n), c’est-à-dire linéaire.
Remarque : Il s’agit ici de la complexité dans le pire des cas. Dans le meilleur des cas, la complexité est O(1).

Exemple 4 :
n X
n
i . j 2.
X
On écrit deux fonctions qui renvoient :
i =1 j =1

1 def deuxfor1(n) :
2 s=0
3 for i in range(1,n+1) :
4 for j in range(1,n+1) :
5 s+=i*j**2
6 return s

7 def deuxfor2(n) :
8 s=0
9 t=0
10 for i in range(1,n+1) :
11 s+=i
12 for j in range(1,n+1) :
13 t+=j**2
14 return s*t
Pour la fonction deuxfor1, on effectue :
• 1 affectation,
• une boucle for de longueur n avec, à chaque itération, une boucle for de longueur n avec 1 addition, 1 produit et 1
carré, soit 3n opérations à chaque itérations,
• 1 renvoi.

4
Le nombre total d’opérations est donc : 1 + n.3n + 1 = O(n 2 ).
La complexité est donc O(n 2 ), c’est-à-dire quadratique.
Pour la fonction deuxfor2, on effectue :
• 2 affectations,
• une boucle for de longueur n avec, à chaque itération, 1 addition,
• une boucle for de longueur n avec, à chaque itération, 1 addition et 1 carré,
• 1 produit et 1 renvoi.
Le nombre total d’opérations est donc : 2 + n + 2n + 2 = O(n).
La complexité est donc O(n), c’est-à-dire linéaire.
Remarque : La complexité de deux boucles for imbriquées est plus grande que celle de deux boucles for qui se suivent, il
ne faut donc imbriquer des boucles for que lorsque cela est indispensable.

3.5 Cas particulier : ajout d’un élément à une liste

On peut utiliser deux méthodes pour ajouter un élément x à la fin d’une liste l :
• l=l+[x]
• l.append(x)
Ces deux méthodes donnent le même résultat mais n’ont pas la même complexité. On peut le voir sur un exemple :
1 def test1(n) :
2 l=[]
3 t=time.time()
4 for i in range(n) :
5 l=l+[0]
6 return time.time()-t
1 def test2(n) :
2 l=[]
3 t=time.time()
4 for i in range(n) :
5 l.append(0)
6 return time.time()-t
On suppose ici qu’on a importé le module time, la fonction time.time donne le temps écoulé en secondes depuis le 1er
janvier 1970. Ainsi les deux fonctions écrites renvoient le temps mis par l’ordinateur pour créer une liste constituée de n
zéros. Le résultat renvoyé dépend donc de l’ordinateur utilisé.

On obtient les résultats suivants :

>>> test1(100000)
14.64185619354248
>>> test2(100000)
0.0
B Il est préférable d’utiliser la méthode .append pour ajouter un élément à une liste plutôt que la concaténation.
En effet, le coût de .append est d’une opération alors que lorsqu’on effectue l=l+[x], la liste l est copiée, le coût est donc
de len(l) opérations. On peut voir que la liste est copiée avec le test suivant :

>>> l=[1,2,3,4]
>>> t=l
>>> l.append(5)
>>> l
[1,2,3,4,5]
>>> t
[1,2,3,4,5]
>>> l=l+[6]
>>> l
[1,2,3,4,5,6]
>>> t
[1,2,3,4,5]

5
IV Exemple : Recherche d’un mot dans une chaîne de caractères
On considère la fonction suivante :
1 def RechercheMotIci(chaine,mot,i) :
2 ” ’Recherche si le mot est dans la chaine de caracteres a partir de l’indice i” ’
3 if len(mot)+i>len(chaine) :
4 return False
5 else :
6 k=0
7 while k<len(mot) and chaine[k+i]==mot[k] :
8 k+=1
9 if k==len(mot) :
10 return True
11 else :
12 return False

Cette fonction renvoie True si le mot est dans la chaîne à la position i et False sinon. Par exemple :
• RechercheMotIci(’vive Python !’,’Python’,5)=True,
• RechercheMotIci(’vive Python !’,’Python’,4)=False,
• RechercheMotIci(’vive Python !’,’Pyton’,5)=False.

On notera n=len(chaine) et p=len(mot).

Calcul de la complexité spatiale :
Les variables stockées sont : une chaîne de caractères de taille n, une chaîne de caractères de taille p, deux entiers i et k.
Comme n + p + 2 = 0(n + p), la complexité spatiale est : O(n + p).
Calcul de la complexité temporelle :
On effectue :
• 1 comparaison avec au plus :
• 1 affectation,
• une boucle while de longueur au plus p avec, à chaque itération, 2 comparaisons et 1 addition,
• 1 comparaison avec, dans tous les cas, 1 renvoi.
Le nombre total d’opérations est donc : 1 + 3p + 2 = O(p).
La complexité est donc O(p).
On considère maintenant la fonction suivante, qui renvoie True si un mot est dans une chaîne de caractères (à n’importe
quelle position) et False sinon.
1 def RechercheMot(chaine,mot) :
2 ” ’Recherche si un mot est dans la chaine” ’
3 i=0
4 while i<=len(chaine)-len(mot) and RechercheMotIci(chaine,mot,i)==False :
5 i+=1
6 if i==len(chaine)-len(mot)+1 :
7 return False
8 else :
9 return True

Calcul de la complexité spatiale :

Les variables stockées sont : une chaîne de caractères de taille n, une chaîne de caractères de taille p, un entier i et, lors de
l’appel à la fonction RechercheMotIci, un entier k. Comme n + p + 2 = 0(n + p), la complexité spatiale est : O(n + p).
Calcul de la complexité temporelle :
On effectue :
• 1 affectation,
• une boucle while de longueur au plus n − p avec, à chaque itération, 2 comparaisons, un appel à RechercheMotIci de
complexité O(p) et 1 addition,
• 1 comparaison avec, dans tous les cas, 1 renvoi.
Le nombre total d’opérations est donc : 1 + (n − p)(2 + O(p)) + 2 = O(p(n − p)).
La complexité est donc O(p(n − p)) ou, en majorant encore, O(np).

6
V Exemple : Recherche par dichotomie
Dans toute la suite, on considère une liste l d’entiers, triée par ordre croissant. On va étudier la fonction suivante, qui
renvoie True si l’entier x est dans la liste l et False sinon.

1 def recherchedicho(l,x) :
2 ” ’Recherche, par la méthode de dichotomie, si un élément x est dans une liste l
triée par ordre croissant. ” ’
3 l.sort()
4 i=0
5 j=len(l)
6 while i<j-1 :
7 k=(i+j)//2
8 if x<l[k] :
9 j=k
10 else :
11 i=k
12 if x==l[i] :
13 return True
14 else :
15 return False

• Tableau d’avancement pour recherchedicho([0,2,3,8,12],3) :

i 0 ... ... ... ... ... ...

j 5 ... ... ... ... ... ...
k 2 ... ... ... ... ... ...

A la fin de la boucle while, on a : i=. . .. . . donc l[i]=. . .. . . ainsi recherchedicho([0,2,3,8,12],3) renvoie : . . . . . . . . . . . . . . . . . . .

• Tableau d’avancement pour recherchedicho([0,2,3,8,12],9) :

i 0 ... ... ... ... ... ...

j 5 ... ... ... ... ... ...
k 2 ... ... ... ... ... ...

A la fin de la boucle while, on a : i=. . .. . . donc l[i]=. . .. . . ainsi recherchedicho([0,2,3,8,12],3) renvoie : . . . . . . . . . . . . . . . . . . .

Dans les calculs qui suivent, on ne considèrera pas la ligne 3, donc on n’évaluera pas le coût du tri. On posera n=len(l).
Calcul de la complexité spatiale :
Les variables stockées sont : une liste de taille n, 4 entiers x, i , j et k. Comme n + 4 = 0(n), la complexité spatiale est : O(n),
c’est-à-dire linéaire.
Calcul de la complexité temporelle :
On effectue :
• 2 affectations,
• une boucle while de longueur au plus N (que l’on déterminera dans la suite) avec, à chaque itération, 1 comparaison,
1 affectation, 1 addition, 1 division, 1 comparaison avec dans tous les cas 1 affectation,
• 1 comparaison avec, dans tous les cas, 1 renvoi.
Le nombre total d’opérations est donc : 2 + 6N + 2 = 0(N ).

De plus, à chaque itération la longueur de la liste est divise par 2, donc, après N passages dans la boucle, la longueur de
la liste est majorée par 2nN . Or la boucle s’arrête lorsque la longueur de la liste est inférieure ou égale à 2. Or :

n ln(n)
≤ 2 ⇔ n ≤ 2N +1 ⇔ ln(n) ≤ (N + 1) ln(2) ⇔ −1 ≤ N.
2N ln(2)
Ainsi : N = O(ln(n)).
La complexité est donc O(ln(n)) c’est-à-dire logarithmique.