Complexité temporelle d’un algorithme

En informatique, le traitement de certains algorithmes complexes peut nécessiter du temps et de la ressource machine : c’est ce qu’on appelle le coût de l’algorithme. L’utilisation des ressources est fondamentale et la question du coût est donc centrale en informatique.
Ce coût est calculable et reflète son efficacité : plus l’algorithme est coûteux, moins il est efficace, et pour une même tâche certains algorithmes se révèlent plus coûteux que d’autres.

L’idée centrale est de donner un calcul du coût de l’algorithme en comptant les opérations fondamentales. Ce calcul n’est pas exact : c’est un ordre de grandeur écrit avec une fonction mathématique.

La mesure du temps d’exécution se fait rarement de façon exacte, si on arrive à comparer deux progammes en estimant leur coût, on dira que l’un a une meilleure complexité temporelle. Notre objectif est donc de cataloguer les algorithmes en les rangeant dans des familles suivants leur complexité. Cette complexité est donnée par une fonction mathémathique qui est un ordre de grandeur noté O (qui est une fonction de n ), voici les principales:

1.O(1) : complexité constante .
2.O(log(n)) : complexité logarithmique (recherche dichotomique).
3.O(n) : complexité linéaire (recherche séquentielle d’une occurence).
4.O(n.log(n)) : complexité quasi­linéaire.
5.O(n^2) : complexité quadratique (tri par insertion).
6.O(2^{ polynôme(n)}) : complexité exponentielle.


Ressources