Une caractérisation du taux de croissance du temps d'exécution d'un algorithme en fonction de la taille de l'entrée, généralement exprimée de manière asymptotique (p. ex. Big O) pour comparer l'évolutivité.

Principe

L'utilisation des ressources est abstraite en fonctions de la taille d'entrée de sorte que les termes dominants déterminent le comportement asymptotique, permettant des comparaisons indépendantes des constantes propres à la machine.

Démonstration

Quicksort a une complexité temporelle moyenne O(n log n), tandis que le tri par insertion a un pire cas O(n^2) ; pour de grands n, Quicksort est plus évolutif malgré des facteurs constants.

Mauvaise application

Utiliser Big O comme un temps d'exécution exact, ignorer la distinction moyen vs pire cas, ou choisir des algorithmes uniquement par classe asymptotique lorsque les constantes et les distributions d'entrée importent.

Conséquence

Un usage approprié informe le choix d'algorithmes, prédit les tendances de performance pour de grandes entrées et oriente les compromis théoriques de complexité en conception et optimisation.

Inversion

Se concentrer uniquement sur les facteurs constants et les microbenchmarks sans tenir compte de la croissance asymptotique, ce qui peut masquer une mauvaise évolutivité pour de grandes entrées.

Limite

Concerne le temps en tant que ressource abstraite mesurée par rapport à la taille d'entrée ; exclut les détails dépendant de l'implémentation, les optimisations spécifiques au matériel et les ressources non temporelles comme la mémoire ou l'énergie (sauf inclusion explicite).

Tension sémantique

Est souvent confondue avec le temps d'exécution empirique ou « efficacité » ; la complexité temporelle est une abstraction asymptotique basée sur un modèle, non une métrique de performance exacte.

Synthèse

La complexité temporelle algorithmique est la description asymptotique de la croissance du temps d'exécution d'un algorithme en fonction de la taille d'entrée, utilisée pour évaluer l'évolutivité et guider le choix d'algorithmes sous modèles de coût idéalisés.