Leçons de niveau 14

Complexité algorithmique/Introduction

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche
Début de la boite de navigation du chapitre
Introduction
Icône de la faculté
Chapitre no 1
Leçon : Complexité algorithmique
Retour auSommaire
Chap. suiv. :Complexité descriptive
fin de la boite de navigation du chapitre
Icon falscher Titel.svg
En raison de limitations techniques, la typographie souhaitable du titre, « Complexité algorithmique : Introduction
Complexité algorithmique/Introduction
 », n'a pu être restituée correctement ci-dessus.

Il est important, dans un souci de performance, d'évaluer la « qualité » d'un algorithme. Ce souci de performance peut être compris de deux manières différentes : soit en temps d'exécution du programme, soit en termes de stockage.

Notre première partie portera donc sur l'évaluation de la complexité en terme temporel.

Complexité temporelle[modifier | modifier le wikicode]

La complexité d'un algorithme donnée est le nombre d'opérations élémentaires nécessaires à son évaluation. On appelle opération élémentaire toute opération du type affectation, comparaison, opérations arithmétiques.

On s'intéresse alors au comportement asymptotique de cette mesure en fonction de la taille des données passées à l'algorithme. On définit donc des ordres de grandeur, nous permettant de classer des algorithmes en fonction de leur temps d'exécution. C'est le premier pas vers la recherche d'une meilleure performance, c'est-à-dire d'une amélioration de la complexité.

Pour déterminer la complexité, il y a trois mesures que l’on peut utiliser :

  1. la durée maximale :  ;
  2. la durée minimale :  ;
  3. la durée moyenne : c’est la moyenne des temps d'exécution,

est le temps d'exécution de l'algorithme associée aux données d'entrée .

Remarque. On utilisera alors la notation de Landau.

  • signifie que la complexité de l'algorithme étudié est majoré une quantité du type .
  • De même, signifie que a une complexité asymptotique négligeable devant  : .
Panneau d’avertissement Il est important de comprendre que dire : "Tel algorithme est d'ordre o(x)", signifie qu’il aura une complexité inférieure ou égale à l’ordre x ET que x est le plus petit ordre supérieur à la complexité de notre algorithme.

Principaux ordres de grandeurs[modifier | modifier le wikicode]

  • o(1) : Il s'agit de l’ordre de grandeur constant. C'est-à-dire que son exécution est indépendante des variables.
Début de l'exemple
Fin de l'exemple
  • o(n) : Ordre de grandeur linéaire. Il dépend des variables de manière linéaire.
Début de l'exemple
Fin de l'exemple
  • o() : C'est la complexité quadratique. Cela signifie que l'exécution sera liée à l'échelle du carré des variables.
Début de l'exemple
Fin de l'exemple
  • o() : C'est la complexité cubique. Cela signifie que l'exécution sera liée à l'échelle du cube des variables.
Début de l'exemple
Fin de l'exemple
  • o() : C'est une complexité exponentielle: le temps d'exécution dépend de façon exponentielle de la taille des variables.
  • o() : C'est un complexité factorielle.

De manière générale, le temps d'exécution est borné par une fonction f(n), n étant la "taille" des variables (cette taille peut être définie comme le plus grand nombre à calculer, ou le nombre de variables, etc.). Si la fonction f(n) est un polynôme (par exemple, 1, n, , ), on dit que la complexité est polynomiale. Si f(n) est un logarithme, alors la complexité sera dite logarithmique (et le temps d'exécution sera plus rapide que pour une complexité polynomiale, lorsque les valeurs de n grandissent). Si f(n) contient n dans un exposant, alors la complexité sera dite exponentielle (et le temps d'exécution sera plus lent que pour une complexité polynomiale, lorsque les valeurs de n grandissent).

Complexité de stockage[modifier | modifier le wikicode]

La complexité en termes de stockage définit la taille en mémoire de l'algorithme ainsi que la taille des variables utilisées.