Algorithmique 

Avancée et 
Complexité
Analyse de Complexité
Université Abou­Bakr Belkaïd ­ Tlemcen
2018/2019

Mahfoud Houari
[Link]@[Link]
 Introduction générale
Quelques paradigmes de programmation
Résumé du cours précédent :

1. Plusieurs catégories de problèmes : (in)décidables, faciles, 
difficiles, admettant des solutions exactes/approchées.
2. Concevoir  un  bon  algorithme  nécessite  d'appliquer  un 
schéma d'algorithmes ou une heuristique.
3. Notions d'efficacité et d'optimalité.
efficacité

⇒ Comment mesurer l'efficacité d'un algorithme ?
 Complexité
Quelques paradigmes de programmation

Coût d'un algorithme 
(Complexité)
 Complexité
Quelques paradigmes de programmation
Pourquoi mesurer le coût d'un algorithme ?

1. Majorer  les  ressources  (mémoire  et  temps)  nécessaires 

pour l'exécution d'un algorithme.
2. Décider  théoriquement  si  l'algorithme  est  efficace : 
pourra  t­il  répondre  en  consommant  une  quantité 
raisonnable de ressources ? (selon un certain contexte).
3. Étant  donnés  deux  algorithmes  répondant  au  même 
problème, lequel est le plus efficace ?
4. Pouvoir  classer  un  problème  à  travers  le  coût  de 
l'algorithme qui le résout.
  ⇒ Rappelons l'intérêt de telle classification 
 Complexité
Quelques paradigmes de programmation
Mesurer le coût à la base de quelle ressource ?

1. Le temps : Complexité temporelle.
2. La mémoire : Complexité spatiale.
3.  Autre : nombre de processus, la bande passante,...

Quelle complexité doit­on considérer ?
Temporelle, spatiale ou un compromis entre les deux 
(tout dépend du contexte)
 Complexité
Quelques paradigmes de programmation
Alors, c'est quoi le coût d'un algorithme ?
1.  C'est le nombre total d'opérations élémentaires.
2.  Pour simplifier, toutes les opérations suivantes ont un coût égal à 1 :
●
Une instruction basique (:=,+,­,*, <, return,...).
●
L'accès à la valeur d'un objet (ou élément d'un tableau).
●
La définition d'une variable.
3.  Le coût  d'une boucle  c'est le  coût du bloc de la  boucle multiplié par le 
nombre d'itérations de cette boucle.
4. Le coût d'un branchement conditionnel (if else) est celui du bloc le plus 
gourmand de ce branchement.
5.  Le coût d'un appel d'une fonction c'est le coût du corps de cette fonction.
6. Le  coût  peut  être  constant  comme  il  peut  dépendre  de  la  taille  des 
données (ou juste une partie des données).
 Complexité
Quelques paradigmes de programmation
Coût d'un algorithme – Exemples

Exemple 1 : Exemple 2 :
boolean R = (X == 3) ; …………...3 boolean listeVide (LC L){
R = ([Link]() == 3) ; ………….....3 return (L.tête == null) ;
R = ([Link]() == [Link]()) ; ...4 }

Coût = 3.
Coût constant
 Complexité
Quelques paradigmes de programmation
Coût d'un algorithme – Exemples

Exemple 3 :
LC mystère (LC L1, LC L2){
   Pointeur P = L1.tête ; ………….3

   While ([Link] != null) do …..2*|L1 ­ 1| + 2
 { P = [Link] ; } ………….2*|L1­ 1|

   [Link] = L2.tête ; ………….3

   return L1 ; ………………………..1
}
Coût : 4*|L1 ­ 1| + 9.
Coût variable.
 Complexité
Quelques paradigmes de programmation
Types de complexité :

1. Dans le pire des cas : Worst Case Complexity

Considérer le cas du problème nécessitant le plus de ressources.

2. Dans le meilleur des cas : Best Case Complexity

Considérer le cas du problème nécessitant le moins de ressources.

3. En moyenne : Average Case Complexity

Considérer  tous  les  cas  du  problème  et  calculer  leur  coût  selon 
leur  probabilité  d'apparition.  Le  coût  total  est  la  somme  de  tous 
ces coûts calculés.

« C'est une complexité probabiliste »
 Complexité
Quelques paradigmes de programmation
Ordres de grandeur asymptotique :
Pour  faciliter  la  comparaison  entre  deux  algorithmes  on  ne 
compare pas entre leurs coûts exactes mais plutôt entre leurs 
ordres  de  grandeur  asymptotiques  (i.e.  entre  les  les  bornes 
supérieures de leurs coûts).

Exemple 3 :

●
n3 + 2.n2 +15   peut être bornée par  n3.

●
Un algorithme A ayant le coût n3 + 2.n2 +15 et moins efficace 
par rapport à un autre ayant le le coût n2 + 3.n + 20.

●
Un algorithme A ayant le coût n3 + 2.n2 +15 et un autre ayant le 
le coût n3 + 20  ont théoriquement la même complexité (borne).
 Complexité
Quelques paradigmes de programmation
Ordres de grandeur asymptotique (notation O) :

Exemple 4 :

2/3 n2 + 1/2 n   =   O(n2) choisir plutôt une borne supérieure 

2/3 n2 + 1/2 n   =   O(n3)  la plus proche possible

log(n)        =   O(n)
[Link](n)    =   O(n2)
 Complexité
Quelques paradigmes de programmation
Ordres de grandeur asymptotique :

Exemple 5 :

√n
n +         =  O(n)
2n n
n + log(n)  =  O(n)
n + [Link](n)  =  O([Link](n))
n + [Link](n)  =  O(n2) (faux)
√n
n  + [Link](n)  = O(n )
2 2

√n √n
n.       + [Link](n)  = O(n.      ) log n
 Complexité
Quelques paradigmes de programmation
Classes de complexité :
1.  Constante :  O(1)
2.  Linéaire : O(n)
3.  Logarithmique :  O(log n)
4.  Quasi­linéaire :  O(n log n)
5.  Quadratique :  O(n2)
6.  Cubique :  O(n3)
7.  Polynomiale :  O(nk)
8.  Exponentielle :  O(kn) pour k > 1.
9.  Quasi­exponentielle :  O(nlog n)
10.  Factorielle :  O(n!)
 Complexité
Quelques paradigmes de programmation
Remarques :
●
Un algorithme est praticable si sa complexité est polynomiale.
●
Un  algorithme  est  optimal  s'il  n'y  a  pas  un  autre  algorithme  qui  a 
une complexité pire cas plus petite.
●
Un  problème  est  classé  linéaire  si  tous  les  algorithmes  le  résolvant 
ont une complexité linéaire (pareil pour les autres classes de complexité).
●
Une  complexité  exponentielle  dépasse  toute  autre  complexité 
polynomiale pour des données assez grandes.
●
La  complexité  temporelle  dépend  généralement  de  la  complexité 
spatiale.
●
On  s'intéresse  aux  complexités  polynomiales  (O(nK))  vu  qu'en 
pratique il est rare de dépasser l'ordre O(n5).
●
Pour  un  problème  qui  n'admet  pas  un  algorithme  praticable,  on 
s'intéresse à trouver une solution approximative qui doit être praticable.
 Complexité
Quelques paradigmes de programmation
Exemples de temps d'exécution :
Temps  d'exécution  de  neuf  algorithmes  en  supposant  que  chaque 
instruction prend 0,1 nanoseconde (processeur ayant plus de 6 GHZ).
 Complexité
Quelques paradigmes de programmation
Exemples d'analyse de complexité (1) :

public int [] Existe(int E, int [] A) {
int i = 0 ;      2
while ( i < [Link] ){   2.|A| + 2  
if ( E == A[i] )      2.|A|  
return true ;    1
i++ ;   2.|A|
}
return false ;        1
}
WCC : ???
BCC  : ???
 Complexité
Quelques paradigmes de programmation
Exemples d'analyse de complexité (1) :

public int [] Existe(int E, int [] A) {
int i = 0 ;      2
while ( i < [Link] ){   2.|A| + 2  
if ( E == A[i] )      2.|A|  
return true ;    1
i++ ;   2.|A|
}
return false ;        1
}
WCC : 6 + 6.|A|  = O(|A|).
BCC  : 5 ou 7  = O(1).
 Complexité
Quelques paradigmes de programmation
Exemples d'analyse de complexité (2) :
On  veut  tester  si  un  élément  E  appartient  à  un  arbre  binaire 
composé de N nœuds. Quelle est la complexité de ce problème ?
public boolean existe(Arbre A, int E) {
if (A == null)  1
return false ;  1
    else if ([Link]() == E) 2
return true ; 1
else
return existe([Link](), E) || existe([Link](), E) ; 4 + Cfg+ Cfd
}
 Complexité
Quelques paradigmes de programmation
Exemples d'analyse de complexité (2) :
On  veut  tester  si  un  élément  E  appartient  à  un  arbre  binaire 
composé de N nœuds. Quelle est la complexité de ce problème ?
public boolean existe(Arbre A, int E) {
if (A == null)  1
return false ;  1
    else if ([Link]() == E) 2
return true ; 1
else
return existe([Link](), E) || existe([Link](), E) ; 4 + Cfg+ Cfd
}

BCC : 2 = O(1).
WCC : 7 + Cfg+ Cfd = ?????
 Complexité
Quelques paradigmes de programmation
Exemples d'analyse de complexité (2) :
On  veut  tester  si  un  élément  E  appartient  à  un  arbre  binaire 
composé de N nœuds. Quelle est la complexité de ce problème ?
public boolean existe(Arbre A, int E) {
if (A == null)  1
return false ;  1
    else if ([Link]() == E) 2
return true ; 1
else
return existe([Link](), E) || existe([Link](), E) ; 4 + Cfg+ Cfd
}

BCC : 2 = O(1).
WCC : 7 + Cfg+ Cfd  = O(N).
 Complexité
Quelques paradigmes de programmation
Exemples d'analyse de complexité (3) :
public int puissance(int X, int N) :
if (X == 0) 
return 1 ;
else if (N == 1)
return X ;
else {
int demi = puissance(X, N / 2) ; 3 + CN/2
  if (N % 2 == 0)
return demi * demi ;
else
return demi * demi * X ;
}
}
BCC : ???.
WCC : ???.
 Complexité
Quelques paradigmes de programmation
Exemples d'analyse de complexité (3) :
public int puissance(int X, int N) :
if (X == 0)  1
return 1 ; 1
else if (N == 1) 1
return X ; 1
else {
int demi = puissance(X, N / 2) ; 3 + CN/2
  if (N % 2 == 0) 2
return demi * demi ; 2
else
return demi * demi * X ; 3
}
}
BCC : ???.
WCC : ???.
 Complexité
Quelques paradigmes de programmation
Exemples d'analyse de complexité (3) :
public int puissance(int X, int N) :
if (X == 0)  1
return 1 ; 1
else if (N == 1) 1
return X ; 1
else {
int demi = puissance(X, N / 2) ; 3 + CN/2
  if (N % 2 == 0) 2
return demi * demi ; 2
else
return demi * demi * X ; 3
}
}
BCC : 2 = O(1).
WCC : 10 + CN/2 = 10 + 10 + CN/4 =…..= 10*log2(N) = O(log2(N)).
 Complexité
Quelques paradigmes de programmation
Exemples d'analyse de complexité (4) :
On  veut  tester  si  un  élément  E  appartient  à  un  ABR  complet 
composé de N nœuds. Quelle est la complexité de ce problème ?
public boolean existe(Arbre A, int E) {
if (A == null)  1
return false ;  1
    else if ([Link]() == E) 2
return true ; 1
else if ([Link]() > E) 2
return existe(A.fils_gauche(), E) ;    2 + Cfg
else
return existe(A.fils_droit(), E) ;   2 + Cfd
}
BCC : 2 = O(1).
WCC : 7 + Cfd = 7 + 7 + Cfd =…..= 7*log2(N) = O(log2(N)).