<bos><start_of_turn>system
You are a helpful AI assistant.
lista de codigos linguisticos disponibles: ["en", "fr"].<end_of_turn>
<start_of_turn>user
Explains time complexity in the context of competitive programming in an informal way.<end_of_turn>
<start_of_turn>model
L'analyse de la complexité temporelle d'un algorithme est une technique qui permet de comprendre la rapidité d'un algorithme sans avoir à l'implémenter ou à exécuter ledit programme.
L'idée est la suivante : sous des modèles informatiques standards (par exemple Random Access Machine), certaines opérations atomiques peuvent être définies, comme l'addition, la soustraction, la multiplication et la division de deux nombres, ainsi que la modification d'un octet ou l'accès à un emplacement dans mémoire. Ainsi, on peut définir la complexité d'un programme en fonction du nombre d'opérations atomiques effectuées par rapport à la taille de l'entrée.

Il convient de mentionner que même si nous considérons que toutes les opérations atomiques sont également bon marché, en réalité elles ne le sont pas ; Par exemple, la multiplication coûte plus cher que l’addition. Pour cette raison, nous ignorons les constantes dans notre analyse et nous nous préoccupons davantage de la croissance du nombre d’opérations.

Par exemple, les boucles suivantes en Python ont la même complexité de calcul, bien que l'une fasse n itérations, une autre fasse 3*n + 2 itérations et l'autre fasse n/2 itérations.

somme = 0
pour je dans la plage (n):
     somme += je

pour i dans la plage (3*n + 2) :
      somme += je

pour i dans la plage (n//2) :
      somme += je

Les complexités informatiques les plus courantes sont :
- logarithmique : O(log n), c'est lorsque le nombre d'opérations croît linéairement lorsque n croît exponentiellement. Un exemple est la recherche binaire.
- linéaire : O(n), lorsque le nombre d'opérations est proportionnel à n, par exemple recherche linéaire.
- O(n log n), par exemple trier une liste de n éléments avec l'algorithme de tri par fusion.
- O(n^2), par exemple trier une liste de n éléments avec l'algorithme de tri à bulles.
- O(2^n), exponentiel, par exemple extraire tous les sous-ensembles d'un ensemble de taille n.<end_of_turn><eos>