MP, PSI et la TSI

Complexité et optimalité des algorithmes

I. Introduction

Quand on tente de résoudre un problème, la question se pose souvent du choix d'un algorithme. Quels critères peuvent guider ce choix ? Deux besoins contradictoires sont fréquemment en présence : l'algorithme doit :

Etre simple à comprendre, à mettre en œuvre, à mettre au point.

Mettre intelligemment à contribution des ressources de l'ordinateur et, plus précisément, il doit s'exécuter le plus rapidement possible.

Si un algorithme ne doit servir qu'un petit nombre de fois, le premier critère est le plus important. Par contre, s'il doit être employé souvent, le temps d'exécution risque d'être un facteur plus déterminant que le temps passé à l'écriture.

L’étude de la complexité des algorithmes a pour objectif l’estimation du coût d’un algorithme. Cette mesure permet donc la comparaison de deux algorithmes sans avoir à les programmer.

Si l’on prend en compte pour l’estimation de la complexité les ressources de la machine telles que la fréquence d’horloge, le nombre de processeurs, le temps d’accès disque etc., on se rend compte immédiatement de la complication voire l’impossibilité d’une telle tâche. Pour cela, on se contente souvent d’estimer la relation entre la taille des données et le temps  d’exécution, et ceci indépendamment de l’architecture utilisée.

Il s’agit d’un modèle simplifié qui tient compte des ressources technologiques ainsi que leurs coûts associés.
 On prendra comme référence un modèle de machine à accès aléatoire et à processeur unique où les opérations sont exécutées l’une après l’autre sans opérations simultanées.

Dans ce modèle, on appelle opérations élémentaires les opérations suivantes :

  • Un accès mémoire pour lire ou écrire la valeur d’une variable ou d’une case d’un tableau ;
  • Une opération arithmétique entre entiers ou réels telle que l’addition, soustraction, multiplication, division ou calcul du reste d’une division entière ;
  • Une comparaison entre deux entiers ou réels.

Exemple :

L’instruction « c <- a + b ; »  nécessite les quatre opérations élémentaires suivantes :

  • Un accès mémoire pour la lecture de la valeur de a,
  • Un accès mémoire pour la lecture de la valeur de b,
  • Une addition de a et b,
  • Un accès mémoire pour l’écriture de la nouvelle valeur de c.

On définit ainsi la complexité (temporelle) d’un algorithme comme étant la mesure du nombre d’opérations élémentaires T (n) qu’il effectue sur un jeu de données n. La complexité est exprimée comme une fonction de la taille du jeu de données.

Pour comparer des solutions entre-elles, deux méthodes peuvent être utilisées :

  • Méthode empirique
  • Méthode mathématique

1. Méthode empirique

Elle consiste à coder et exécuter deux (ou plus) algorithmes sur une batterie de données générées d’une manière aléatoire

À chaque exécution, le temps d’exécution de chacun des algorithmes est mesuré.

Ensuite, une étude statistique est entreprise pour choisir le meilleur d’entre-eux à la lumière des résultats obtenus.

Problème !

Ces résultats dépendent 

  • La machine utilisée ;
  • Jeu d’instructions utilisées
  • L’habileté du programmeur
  • Jeu de données générées
  • Compilateur choisi
  • L’environnement dans lequel est exécuté les deux algorithmes (partagés ou non)

2. Méthode mathématique

Pour pallier à ces problèmes, une notion de complexité plus simple mais efficace a été proposée par les informaticiens.

Ainsi, pour mesurer cette complexité, la méthode mathématique consiste non pas à la mesurer en secondes, mais à faire le décompte des instructions de base exécutées par ces deux algorithmes.

Cette manière de procéder est justifiée par le fait que la complexité d’un algorithme est en grande partie induite par l’exécution des instructions qui le composent.

Cependant, pour avoir une idée plus précise de la performance d’un algorithme, il convient de signaler que la méthode expérimentale et mathématique sont en fait complémentaires.

II. Différentes formes de complexité

Il est évident de la remarque précédente que la complexité d’un algorithme peut ne pas être la même pour deux jeux de données différents. Ceci peut avoir des conséquences sur le choix du meilleur algorithme pour un problème donné.

Nous notons Dn l’ensemble des données de taille n et C(d) le coût de l’algorithme sur la donnée d.

On définit 3 types de complexité :

  • Complexité au meilleur

  • Complexité au pire

  • Complexité moyenne

1. Complexité dans le pire des cas (Worst case)


C’est le plus grand nombre d’opérations qu’aura à exécuter l’algorithme sur un jeu de données de taille fixée, ici à n.


Avantage : il s’agit d’un maximum, et l’algorithme finira donc toujours avant d’avoir effectué Tmax(n) opérations.

Inconvénient : cette complexité peut ne pas refléter le comportement « usuel » de l’algorithme. Le pire cas ne peut se produire que très rarement, mais il n’est pas rare que le cas moyen soit aussi mauvais que le cas pire.

2. Complexité dans le meilleur des cas (Best case)


C’est le plus petit nombre d’opérations qu’aura à exécuter l’algorithme sur un jeu de données de taille fixée, ici à n. C’est une borne inférieure de la complexité de l’algorithme sur un jeu de données de taille n.

3. Complexité en moyenne (Average case)


Il s’agit de calculer la moyenne (espérance mathématique) des nombres d’opérations élémentaires effectuées sur la totalité des instances. Ce calcul est généralement très difficile et souvent même délicat à mettre en œuvre car il faut connaître la probabilité de chacun des jeux de données pour pouvoir calculer la complexité en moyenne. Cette forme d’analyse fait actuellement l’objet de nombreux travaux de recherche et permet d’expliquer, d’une part le comportement de certains algorithmes en pratique ; et d’autre part, le choix d’algorithmes pour des problèmes ayant des tailles considérables tels que les problèmes d’apprentissage en intelligence artificielle.

Avantage : reflète le comportement « général » de l’algorithme si les cas extrêmes sont rares ou si la complexité varie peu en fonction des données.

Inconvénient : en pratique, la complexité sur un jeu de données particulier peut être nettement plus importante que la complexité en moyenne, dans ce cas la complexité en moyenne ne donnera pas une bonne indication du comportement de l’algorithme. En pratique, nous ne nous intéresserons qu’à la complexité au pire et à la complexité en moyenne.

4. Définition de l’optimalité :

Un algorithme est dit optimal si sa complexité est la complexité minimale parmi les algorithmes de sa classe.
Nous nous intéresserons quasi exclusivement à la complexité en temps des algorithmes. Il est parfois intéressant de s’intéresser à d’autres ressources, comme la complexité en espace (taille de l’espace mémoire utilisé), la largeur de bande passante requise, etc.

5. Illustration : cas du tri par insertion

Problématique  du tri

Données : une séquence de n  nombres, a1, ..., an.


Résultats : une permutation a'i de la séquence d’entrée, telle que a'a'i+1 ∀

Principe  du tri par insertion

De manière répétée, on retire un nombre de la séquence d’entrée et on l’insère à la bonne place dans la séquence des nombres déjà triés (ce principe est le même que celui utilisé pour trier une poignée de cartes).

Algorithme

def Tri_Insertion(L):
          for i in range(1,len(L)):
                     m=L[i]
                     j=i
                     while j>0 and L[j-1]>m:
                                 L[j]=L[j-1]
                                 j-=1
                     L[j]=m
          return L

=> Explication

  • On retire un nombre de la séquence d’entrée.

  • Les i-1 premiers éléments de A sont déjà triés.
  • Tant que l’on n’est pas arrivé au début du tableau, et que l’élément courant est plus grand que celui à insérer.
On décale l’élément courant (on le met dans la place vide).
  • Finalement, on a trouvé où insérer notre nombre.

Complexité

Attribuons un coût en temps à chaque instruction, et comptons le nombre d’exécutions de chacune des instructions. Pour chaque valeur de j∈[2,n] , nous notons tj le nombre d’exécutions de la boucle « while » pour cette valeur de j. Il est à noter que la valeur de tj dépend des données...

def Tri_Insertion(L):                                               // coût         Nombre de fois
          for i in range(1,len(L)):                                  // coût C1 ........ N
                     m=L[i]                                                   // coût C2 ........ N-1
                     j=i                                                          // coût C3 ........ N-1
                     while j>0 and L[j-1]>m:                   // coût C4 ........ 2+3+...+N
                                 L[j]=L[j-1]                               // coût C5  ........ 1+2+...N-1
                                 j-=1                                           // coût C6  ........ 1+2+...N-1
                     L[j]=m                                                 // coût C7 ........ N-1
          return L

Le temps d’exécution total de l’algorithme est alors la somme des coûts élémentaires :

=> Complexité au meilleur :

Le cas le plus favorable pour la fonction Tri_Insertion est quand le tableau est déjà trié.

Dans ce cas tj = 1 pour tout j.



T(npeut ici être écrit sous la forme T(n) = an+b, et étant des constantes indépendantes des entrées, et
 T(nest donc une fonction linéaire  de n.
 Le plus souvent, comme c’est le cas ici, le temps d’exécution d’un algorithme est fixé pour une entrée donnée ; mais il existe des algorithmes « aléatoires » intéressants dont le comportement peut varier même pour une entrée fixée.

=> Complexité au pire :

Le cas le plus défavorable pour l’algorithme Tri_Insertion est quand le tableau est déjà trié dans l’ordre inverse. Dans ce cas t= pour tout j.


T(nest donc de la forme T(n)=an^2 +bn+c

T(n) est donc une fonction quadratique de n.

=> Complexité en moyenne :

Supposons que l’on applique l’algorithme de tri par insertion à n  nombres choisis au hasard. Quelle sera la valeur de t? C’est-à-dire, où devra-t-on insérer A[ j] dans le sous-tableau A[1.. j-1] ?


En moyenne, la moitié des éléments de A[1.. j-1] sont inférieurs à A[ j], et l’autre moitié sont supérieurs. Donc = j/2. Si l’on reporte cette valeur dans l’équation définissant T(n), on obtient, comme dans le cas pire, une fonction quadratique en n.

Ce qui nous intéresse vraiment, c’est l’ordre de grandeur du temps d’exécution. Seul le terme dominant de la formule exprimant la complexité nous importe, les termes d’ordres inférieurs n’étant pas significatifs quand n  devient grand. On ignore également le coefficient multiplicateur constant du terme dominant. On écrira donc, à propos de la complexité du tri par insertion :

  • Complexité au meilleur = Ο(n).
  • Complexité au pire = Ο(n^2).
  • Complexité en moyenne = Ο(n^2).

En général, on considère qu’un algorithme est plus efficace qu’un autre si sa complexité dans le cas pire a un ordre de grandeur inférieur.

6. Classes de complexité

Les algorithmes usuels peuvent être classés en un certain nombre de grandes classes de complexité :

  • O(logn: Les algorithmes sub-linéaires dont la complexité est en général en O(logn).
  • O(n) :  Les algorithmes linéaires en complexité O(n)

  • O(nlogn) : et ceux en complexité en O(nlogn)

  • O(n^k) : Les algorithmes polynomiaux en O(n^k) pour k  > 3
  • Exp(n) : Les algorithmes exponentiels

Les trois premières classes sont considérées rapides alors que la quatrième est considérée lente et la cinquième classe est considérée impraticable.


Partager ce cours avec tes amis :
Rédigé par Mostafa Sedoki
Professeur d'Informatique dans les CPGE

Cours Similaires :