Introduction

Pour résoudre un problème, il peut y avoir plusieurs solutions plus ou moins efficaces :

  • du point de vue de l’utilisation de la mémoire
  • du point de vue du temps de calcul.

On parle de coût ou de complexité mémoire / temporelle.

La complexité mesure l’efficacité d’un algorithme. Elle est indiquée en Ordre de grandeur, en fonction de la taille des données, par convention appelée n.

Différentes complexités existent, celle du meilleur cas, la moyenne, mais celle qui est habituellement retenue comme mesure de l’efficacité de l’algorithme est celle du pire cas.

Pour la complexité en temps de calcul, il est possible de compter le nombre de comparaisons ou d’affectations par exemple, ou encore le nombre d’itérations. En pratique, on choisi de dénombrer l’instruction qui s’exécute le plus.

Souvent, il faut faire un compromis entre le coût en temps et en mémoire.

Le logarithme en base 2

Le logarithme en base 2 est utilisé pour exprimer certaines complexité. Il est défini comme suit : log2(n) = ln(n) / ln(2) ; exemple : log2(100) = 6,64…. Retenir la valeur arrondie à l’entier supérieur ; elle correspond :

  • au nombre de fois qu’il faut diviser un nombre par 2 pour obtenir une valeur inférieure ou égale à 1 ; exemple : 100 / 2 = 50 ; 50 / 2 = 25… (7 divisions) ;
  • ou encore, à la (première) puissance de 2 supérieure au nombre : 27 = 128.

Différents ordres des grandeur

  • Lorsque la complexité ne dépend pas de la taille des données, on est en 0(1) ; exemple : accéder au i-ème élément d’un tableau (complexité constante).
  • une recherche dichotomique (dans un tableau trié) est en O(log2(n)) complexité logarithmique).
  • Pour parcourir un tableau de taille “n”, il faut “n” itérations, ce qui correspond à une complexité en 0(n) (complexité linéaire) ;
  • un algorithme de tri à une complexité
    • en O(n²) ; exemples : tri bulle, par insertion ou par sélection (complexité quadratique) ;
    • en O(n.log2(n)) ; exemples : tri rapide, par tas ou fusion.

Remarque : il existe d’autres formes de complexité (extrêmement coûteuses) : cubique, factorielle et polynomiale.

Complexité théorique 0(1) 0(log2(n)) 0(n) 0(n.log2(n)) 0(n²)
Exemple pour n = 100 1 7 100 700 10000
Exemple pour n = 1000 1 10 1000 10000 1000000