human
Veuillez expliquer ce qu'est la "complexité temporelle"
gpt
En informatique, la complexité du temps est la complexité de calcul qui décrit la quantité de temps informatique nécessaire pour exécuter 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 prend un temps fixe à effectuer.Ainsi, le temps pris et le nombre d'opérations élémentaires effectués par l'algorithme sont considérés comme liés par un facteur constant.
Étant donné que le temps d'exécution d'un algorithme peut varier selon les différentes entrées de la même taille, on considère généralement la complexité de temps le pire des cas, qui est le temps maximum requis pour les entrées d'une taille donnée.La complexité moyenne des cas, qui est la moyenne du temps prise sur les entrées d'une taille donnée est la moins courante, qui est la moyenne du temps prise sur les entrées 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.: 226 Étant donné que cette fonction est généralement difficile à calculer exactement, et le temps d'exécution pour les petites entrées n'est généralement pas consécutif, on se concentre généralement sur le comportementde la complexité lorsque la taille de l'entrée augmente, c'est-à-dire le comportement asymptotique de la complexité.Par conséquent, la complexité temporelle est généralement exprimée en utilisant une notation B



O
(
n
)


{\ displayStyle o (n)}

,



O
(
n
Journal
⁡
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 des 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 apparaissant dans la notation Big O.Par exemple, un algorithme avec complexité temporelle



O
(
n
)


{\ displayStyle o (n)}

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



O
(

n

α


)


{\ displayStyle o (n ^ {\ alpha})}

 Pour une certaine constante



α
>
1


{\ displaystyle \ alpha> 1}

 est un algorithme de temps polynomial.