Bonjour ! Aujourd'hui nous allons voir quelque chose d'un peu plus théorique que d'habitude : la complexité algorithmique.

Je me permets de faire un aparté : n'étant pas un spécialiste de la complexité algorithmique, je ne rentrerai pas dans les détails des opérations mathématiques.

La complexité algorithmique est un moyen mathématique de déterminer la performance d'un algorithme en fonction de la taille et de la nature des données.

Pour mesurer cette performance, nous avons besoin d'évaluer le nombre d'opérations élémentaires (affectation, comparaison...) qui sont effectuées dans l'algorithme étudié.

Il existe quelques configurations caractéristiques pour évaluer un algorithme :

  • Le meilleur cas ;
  • Le pire des cas ;
  • Le cas moyen.

La notation " big oh " est la plus courante. Voici la plupart des notations, par ordre de performance :

  • O(1) : temps constant (très bon)
  • O(logn) : logarithmique (bon)
  • O(n) : linéaire (bon dans certains cas)
  • O(n×logn) : tris (par échanges)
  • O(n²) : quadratique, polynomial (mauvais)
  • O(2n) : exponentiel (problèmes très difficiles)

Ce tableau représente le temps que mettrais un algorithme en O(...) à s'exécuter en fonction de n élément.

tableau complexite

Une représentation un peu plus graphique:fonction complexite

Je vous propose de regarder ensemble quelques petits exemples pour illustrer tout ça:

DÉBUT  n <- 100  POUR compteur <- 0 JUSQU'À n FAIRE    ECRIRE compteur  FINPOURFIN

La complexité de cet algorithme est en O(n) car il faut n instructions pour arriver à la fin de l'algorithme.

DÉBUT  n <- 100  POUR i <- 0 JUSQU'À n FAIRE    POUR j <- 0 JUSQU'À n FAIRE      ECRIRE "i:", i,"j:",j    FINPOUR  FINPOURFIN

Voici une complexité de O(n²), de manière générale, les boucles imbriquées sont en O(n²).

DÉBUT  n <- 100    POUR i <- 0 JUSQU'À 10000 FAIRE    ECRIRE "i:", i  FINPOURFIN

Voici une complexité de O(1), en effet peu importe la taille des données, le nombre d'opérations élémentaires reste constant.

DÉBUT  n <- 20  POUR i <- 0 JUSQU'À n FAIRE    POUR j <- 0 JUSQU'À (n * n) FAIRE      ECRIRE "i:",i, "j:",j    FINPOUR  FINPOURFIN

Cet algorithme est en O(n^3). Regardez bien la condition d'arrêt de la boucle POUR \imbriquée: il faut effectuer n² opérations pour satisfaire la condition.

Pour finir, je vais juste revenir sur l'algorithme du tri à bulles d'hier:

  • Dans le meilleurs cas (le tableau est déjà trié) il est en O(n)
  • Dans le cas moyen il est en O(n²)
  • Dans le pire des cas il est en O(n²)

Le fait que cet algorithme est en majorité du temps en O(n²) fait de lui un "mauvais" algorithme de tri. Nous verrons demain un autre algorithme de tri, théoriquement plus performant que le tri à bulles.

Voilà ! J'espère que ce billet un peu plus théorique que d'habitude vous a plu, rendez-vous demain pour la suite !