Algorithmique et Structures de données

Complexité des algorithmes

Abdelkamel, Ben Ali

Université d’El Oued

Décembre 2020

Licence 2 d’informatique
Théorie de complexité

Théorie de complexité, a pour but de :

Fournir les outils mathématiques nécessaires à l’analyse des
performances d’un algorithme
Avoir une idée de ce qui est faisable et infaisable actuellement
Ce qui permet de :
Améliorer les performances des problèmes faciles
Savoir comment aborder les problèmes difficiles

benali-abdelkamel@[Link] (UE) Alg. et Structures de données 2020-2021 − Semestre 1 2/20

Complexité d’un algorithme

Un programme qui s’exécute consomme de l’espace mémoire

et du temps de calcul :
Complexité temporelle (plus intéressante)
Complexité spatiale
Le but est d’exprimer les performances d’un algorithme à
l’aide de fonctions qui dépendent de la taille des données

TALG (n) = ?

benali-abdelkamel@[Link] (UE) Alg. et Structures de données 2020-2021 − Semestre 1 3/20

Mesures de la complexité

Pour mesurer la complexité temporelle d’un algorithme, on

s’intéresse plutôt aux opérations les plus coûteuses (FLOPS) pour
le problème de calcul particulier :
Racine carrée, Log, Exp, Addition réelle . . .
Comparaisons d’éléments dans le cas des tris . . .
et on calcule le nombre d’opérations fondamentales exécutées par
l’algorithme.

Problème Opérations fondamentales

Recherche d’une valeur dans un comparaisons entre les éléments du
tableau tableau
Multiplication des matrices réelles Multiplication scalaire
Addition des entiers binaires Opération binaire

benali-abdelkamel@[Link] (UE) Alg. et Structures de données 2020-2021 − Semestre 1 4/20

Mesures de la complexité

Le temps de l’exécution dépend de la taille de l’entrée. On veut

considérer seulement la taille essentielle de l’entrée.
Cela peut être par exemple :
le nombre d’éléments combinatoires dans l’entrée
le nombre de bits pour représenter l’entrée
etc . . .

Problème Taille de la donnée

Recherche d’une valeur dans un Nombre d’éléments dans
tableau le tableau
Multiplication des matrices réelles Dimensions des matrices
Addition des entiers Nombre des bits pour représenter les
binaires entiers

benali-abdelkamel@[Link] (UE) Alg. et Structures de données 2020-2021 − Semestre 1 5/20

Mesures de complexité

Complexité moyenne
Complexité dans le pire des cas

Exemple : Pour la recherche séquentielle (exercice TD) dans

un tableau de n éléments, on fait n/2 comparaisons en
moyenne et n comparaisons dans le pire des cas.

benali-abdelkamel@[Link] (UE) Alg. et Structures de données 2020-2021 − Semestre 1 6/20

Mesures de complexité
Soit A un algorithme
Dn l’ensemble des entrées de taille n
I ∈ Dn une entrée

Définition :
1 coutA (I ) = Nb d’opérations fondamentales exécutées par A sur I
2 la complexité de A en pire cas :

MaxA (n) = Max {coutA (I ), I ∈ Dn }

3 Soit Pr une distribution de probabilités sur Dn

la complexité de A en moyenne :
X
MoyA (n) = Pr [I ].coutA (I )
I ∈Dn

benali-abdelkamel@[Link] (UE) Alg. et Structures de données 2020-2021 − Semestre 1 7/20

Mesures de complexité
Exemple : Recherche Séquentielle
int index_of_value ( double v [] , int n , int x )
{
int j = 0;

while ( j < n )
{
if ( v [ j ] == x )
return j ;
j = j + 1;
}

return -1;
}

Opération de base : comparaison de x avec un élément de v .

Complexité en pire cas de RS :

MaxRS (n) = n

benali-abdelkamel@[Link] (UE) Alg. et Structures de données 2020-2021 − Semestre 1 8/20

Mesures de complexité
Complexité en moyenne de RS :
On suppose que :
tous les éléments sont distincts
Pr [x ∈ v ] = q
si x ∈ v alors toutes les places sont équiprobables
Pour 1 ≤ i ≤ n soit
Ii = {(v , x ), x ∈ v }
et
In+1 = {(v , x ), x ∈
/ v}
On a :
Pr [Ii ] = q/n pour 1 ≤ i ≤ n et coutRS (Ii ) = i
et
Pr [In+1 ] = 1 − q et coutRS (In+1 ) = n

benali-abdelkamel@[Link] (UE) Alg. et Structures de données 2020-2021 − Semestre 1 9/20

Mesures de complexité

Pn+1
MoyRS (n) = i=1 Pr [Ii ] · coutRS (Ii )
Pn q q Pn
= i=1 n (i ) + (1 − q) · n = n i=1 (i ) + (1 − q) · n

q n(n+1)
= n · 2 + (1 − q) · n = (1 − q2 ) · n + q
2

si q = 1 alors MoyRS (n) = (n + 1)/2

si q = 1/2 alors MoyRS (n) = (3n + 1)/4

benali-abdelkamel@[Link] (UE) Alg. et Structures de données 2020-2021 − Semestre 1 10/20

Notations utilisées

Il faut comparer les taux d’accroissement de différentes fonctions

qui mesurent les performances d’un algorithme.

Notation ”o”
On dit que f (x ) = o(g(x )) pour x −→ ∞ si

f (x )
lim =0
x −→∞ g(x )

Ce que veut dire que f croı̂t plus lentement que g quand x est très
grand. Par exemple :
x 2 = o(x 5 ) sin x = o(x )
√
14.079 x = o(x /2 + 7 cos x ) 23 log x = o(x 0.002 )

benali-abdelkamel@[Link] (UE) Alg. et Structures de données 2020-2021 − Semestre 1 11/20

Notations utilisées

Notation ”O”
On dit que f (x ) = O(g(x )) s’il existe k et x0 tels que :

x > x0 f (x ) < kg(x )

La notation o est plus précise que O, mais O est plus facile à

calculer et suffisant. Par exemple :

sin(x ) = O(x ) sin x = O(1)

benali-abdelkamel@[Link] (UE) Alg. et Structures de données 2020-2021 − Semestre 1 12/20

Un classement des fonctions

√
log(n)  n  n  n log(n)  n2 
n
n3  2n  exp(n)  n!  nn  22

O(1) Constant
O(log(n)) Logarithmique
O(n) Linéaire
n log(n) n log(n)
O(n2 ) Quadratique
O(n3 ) Cubique
O(2n ) Exponentiel

benali-abdelkamel@[Link] (UE) Alg. et Structures de données 2020-2021 − Semestre 1 13/20

Algorithmes polynomiaux ↔ exponentiels

Complexité polynomiale ⇒ souvent réalisable

∃k > 0, f (n) ∈ O(n k ).
Complexité exponentielle ⇒ en général irréalisable
∃b > 1, b n ∈ O(f (n)).
Complexité doublement exponentielle
n
par exemple : f (n) = 22 .
Complexité sous-exponentielle
√
par exemple : f (n) = 2 n .

√
log(n)  n  n  n log(n)  n 2 
n
n 3  2n  exp(n)  n!  n n  22

benali-abdelkamel@[Link] (UE) Alg. et Structures de données 2020-2021 − Semestre 1 14/20

Comparaison entre les différents groupes de fonctions

2 16 64 256
log log n 0 2 2.58 3
log n 1 4 6 8
n 2 16 64 256
n log n 2 64 384 2048
n2 4 256 4096 65536
2n 4 65536 1.84467e+19 1.15792e+77
n! 2 2.0923e+13 1.26887e+89 8.57539e+506
nn 4 1.84467e+19 3.9402e+115 3.2317e+616
2
2n 16 1.15792e+77 1.04438e+1233 2.00353e+19728

Méga = 106 (220 ), Géga = 109 (230 ), Tera = 1012 (240 ), Péta = 1015 (250 )
4 Ghz pendant 1 an = 1, 26 × 1017
4 Ghz pendant 4 Milliards d’années = 5 × 1026

benali-abdelkamel@[Link] (UE) Alg. et Structures de données 2020-2021 − Semestre 1 15/20

Applications

Recherche dans un tableau

Recherche séquentielle
O(N )
10000 comparaisons dans un tableau de 10000 éléments

Recherche dichotomique
O(log2 N )
14 comparaisons dans un tableau de 10000 éléments

benali-abdelkamel@[Link] (UE) Alg. et Structures de données 2020-2021 − Semestre 1 16/20

Applications
Multiplication de matrices (exercice TD)
Problème classique : C = A × B avec A et B matrices carrés d’ordre n.
n
X
Cij = Aik Bkj
k =1

for ( i = 0; i < n ; i ++)

{
for ( j = 0; j < n ; j ++)
{
C [ i ][ j ] = 0.;
for ( k = 0; k < n ; k ++)
{
C [ i ][ j ] += A [ i ][ k ]* B [ k ][ j ];
}
}
}

Complexité : O(N 3 )
benali-abdelkamel@[Link] (UE) Alg. et Structures de données 2020-2021 − Semestre 1 17/20
Applications

Multiplication de polynômes (Exercice TD)

P = ni=1 ai x i Q= m i
P P
i=1 bi x

PQ = n+m i avec
P P
i=1 ci x ck = i+j =k ai bj
d’où le programme

for ( i = 0; i < n + m ; i ++)

C [ i ] = 0.;
for ( i = 0; i < n ; i ++)
for ( j = 0; j < m ; j ++)
C [ i + j ] += A [ i ]* B [ j ];

Et sa complexité en O(mn)

benali-abdelkamel@[Link] (UE) Alg. et Structures de données 2020-2021 − Semestre 1 18/20

Applications

Tri par sélection (Exercice TD)

void triSelection ( float t [] , int n )

{
int i , j , i_min ;
for ( i = 0; i < n - 1; i ++)
{
i_min = i ;
for ( j = i + 1; j < n ; j ++)
if ( t [ j ] < t [ i_min ])
i_min = j ;
if ( i_min > i )
echanger (t , min , i );
}
}

On fait (n − 1) + (n − 2) + (n − 3) + · · · + 2 + 1 comparaisons
On fait donc n(n − 1)/2 comparaisons → O(n 2 )

benali-abdelkamel@[Link] (UE) Alg. et Structures de données 2020-2021 − Semestre 1 19/20

Applications

Exemple de tri par sélection

i
imin

benali-abdelkamel@[Link] (UE) Alg. et Structures de données 2020-2021 − Semestre 1 20/20