Complexité temporelle

La complexité temporelle est la complexité de calcul qui décrit le temps nécessaire à l'exécution d'un algorithme.

La complexité temporelle est généralement estimée en comptant le nombre d'opérations élémentaires effectuées par l'algorithme, en supposant que chaque opération élémentaire nécessite une durée fixe. Ainsi, la quantité de temps nécessaire et le nombre d’opérations élémentaires effectuées par l'algorithme sont supposés différer d'au plus un facteur constant.

Étant donné que la durée d'exécution d'un algorithme peut varier entre différentes entrées de même taille, on considère généralement la complexité temporelle dans le cas le plus défavorable, qui correspond à la durée maximale requise pour les entrées d'une taille donnée. La complexité de la casse moyenne, qui est la moyenne du temps nécessaire pour les entrées d’une taille donnée, est moins courante et généralement spécifiée explicitement, ce qui est logique dans la mesure où il n’ya qu’un nombre infini d’entrées possibles d’une taille donnée. Dans les deux cas, la complexité temporelle est généralement exprimée en fonction de la taille de l'entrée.

Comme cette fonction est généralement difficile à calculer avec précision et que le temps d’exécution des petites entrées n’est généralement pas consécutif, on se concentre généralement sur le comportement de la complexité lorsque la taille de l’entrée augmente, c’est-à-dire le comportement asymptotique du système. complexité.

Par conséquent, la complexité de temps est généralement exprimé en utilisant grand O notation, typiquement

O (n), {\ displaystyle O (n),} O (n log ⁡ n), {\ displaystyle O (n \ log n),} O (n α), {\ displaystyle O (n ^ {\ alpha})}} O (2 n), {\ displaystyle O (2 ^ {n}),} etc., 

où n est la taille d'entrée en unités de bits nécessaires pour représenter l'entrée.    

Les complexités algorithmiques sont classées en fonction du type de fonction figurant dans la grande notation O. Par exemple, un algorithme de complexité temporelle

O (n) {\ displaystyle O (n)}  

est un algorithme de temps linéaire et un algorithme de complexité temporelle

O (n α) {\ displaystyle O (n ^ {\ alpha})}  

pour une constante

α > 1 {\ displaystyle \ alpha> 1}  

est un algorithme polynomial.