Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Complexité en temps
Résumé
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.
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, 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 , ce qui signifie qu'il existe une constante telle que pour toute entrée de taille le nombre d'étapes sera inférieur à .
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).
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.