Complexité en temps

En algorithmique, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée. Le temps compte le nombre d'étapes de calcul avant d'arriver à un résultat.

Habituellement, le temps correspondant à des entrées de taille n est le temps le plus long parmi les temps d’exécution des entrées de cette taille ; on parle de complexité dans le pire cas. Les études de complexité portent dans la majorité des cas sur le comportement asymptotique, lorsque la taille des entrées tend vers l'infini, et l'on utilise couramment les notations grand O de Landau.

La complexité en temps étant la mesure la plus courante en algorithmique, on parle parfois simplement de la complexité d'un algorithme, mais il existe d'autres mesures comme la complexité en espace.

Calculer les complexités d'un algorithme, et en particulier la complexité en temps est parfois complexe, et cette étude constitue en elle-même une discipline : l'analyse de la complexité des algorithmes.

Définitions

La complexité en temps compte le nombre d'étapes de calcul. Il y a plusieurs façons de définir ces étapes, par exemple le nombre d'opérations dans une machine RAM^[1], ou des mesures plus théoriques comme le nombre de comparaisons dans le cas d'un algorithme de tri ou le nombre de pas d'une machine de Turing.

L'étude du temps de calcul consiste souvent à donner une borne supérieure sur le nombre d'étapes, exprimée par un ordre de grandeur. Par exemple dans le cas de l'algorithme tri fusion, on parle d'une complexité en ${\displaystyle O(n\log(n))}$, ce qui signifie qu'il existe une constante ${\displaystyle a}$ telle que pour toute entrée de taille ${\displaystyle n}$ le nombre d'étapes sera inférieur à ${\displaystyle a\times n\log(n)}$.

Le temps, comme défini plus haut, est lié au temps de calcul réel mais c'est une mesure plus abstraite, qui dépend de l'algorithme et de l'entrée mais est indépendante de la puissance de l'ordinateur par exemple (on compte des étapes de calcul et non des secondes)^[2].

Liste de complexités en temps classiques

Nom	Temps de calcul (T(n))	Exemple de temps de calcul	Exemple d'algorithmes
Constant	O(1)	10	Diminution d'une clé dans un tas de Fibonacci
Logarithmique	O(log n)	log n, log(n^2)	Recherche dichotomique
Linéaire	O(n)	n	Recherche séquentielle, algorithme simple de recherche du plus petit élément d'un tableau
Linéarithmique	O(n log n)	n log n, log n!	Tri fusion
Quadratique	O(n^2)	n^2	Tri par insertion
Cubique	O(n^3)	n^3	Algorithme naïf de multiplication matricielle.
Polynomial	2^O(log n) = poly(n)	n, n log n, n^10	Algorithme de Karmarkar, test de primalité AKS
Quasipolynomial	2^O((log n)O(1))	n^log n	Test d'isomorphisme de graphes de Babai[3]
Sous-exponentiel	2^o(n)	2^n1/3	Meilleurs algorithmes pour la factorisation des entiers
Exponentiel	2^O(n)	1.1^n, 10^n	Algorithme en force brute, par exemple pour le problème du voyageur de commerce

Lien avec la théorie de la complexité des problèmes

La théorie de la complexité des problèmes, souvent abrégée en théorie de la complexité, est la discipline qui consiste à classer les problèmes algorithmiques par difficulté selon diverses mesures. Certaines classes de complexité sont définies par le temps de calcul, par exemple les problèmes de la classe P sont ceux pour lequel il existe un algorithme dont la complexité en temps est bornée par un polynôme^[4].

Parmi les classes de problèmes définie par du temps, on compte notamment P, NP et EXPTIME. En s’intéressant aux algorithmes probabilistes, on obtient des classes comme BPP.

Mesures de complexité alternatives

Une alternative à la complexité dans le pire cas, est de calculer la complexité en moyenne d'un algorithme, c'est-à-dire le temps que mettra l'algorithme en moyenne sur une entrée tirée au hasard, par exemple selon la distribution uniforme. On peut aussi citer l'analyse lisse d'algorithme et la complexité générique.

Certaines mesures de complexités ne sont pas directement liées au temps de calcul, c'est par exemple le cas de la complexité en espace, c'est-à-dire la mesure de la mémoire nécessaire pour faire un calcul.

Notes et références

1. Voir (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, MIT Press, 2009, 3^e éd. [détail de l’édition], chap. 2.2, p. 23.
2. Sylvain Perifel, Complexité algorithmique, Ellipses, 2014, 432 p. (ISBN 9782729886929, lire en ligne), chap. 2.1 (« Temps déterministe »).
3. Isomorphismes de graphes en temps quasi-polynomial, Harald Helfgott, 2017 lire en ligne
4. (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, MIT Press, 2009, 3^e éd. [détail de l’édition], chap. 34, « NP-Completeness ».

• Portail de l'informatique théorique