Complexité algorithmique : notation, analyse du coût en temps et en espace

En 30 secondes

• La complexité en temps compte le nombre d'opérations ; la complexité en espace compte la mémoire supplémentaire utilisée, toutes deux en fonction de la taille n des données.
• La notation O mesure par défaut le pire cas ; le meilleur cas et le cas moyen sont des notions distinctes.
• Boucles successives : les coûts s'additionnent (O(n + n)). Boucles imbriquées : les coûts se multiplient (O(n × n)).

Ce que tu sauras faire

• Distinguer complexité en temps et complexité en espace d'un algorithme.
• Distinguer meilleur cas, pire cas et cas moyen d'un algorithme.
• Déterminer la complexité d'un algorithme simple à partir du nombre d'opérations qu'il effectue.

Les mots à connaître

Complexité algorithmique

une mesure du coût d'exécution d'un algorithme en fonction de la taille n des données traitées, exprimée le plus souvent en nombre d'opérations élémentaires (complexité en temps) ou en quantité de mémoire utilisée (complexité en espace).

Notation O (grand O)

la notation qui exprime une complexité algorithmique dans le pire des cas : O(1) signifie un coût constant, indépendant de n ; O(n) signifie un coût proportionnel à n.

Complexité en temps

le nombre d'opérations élémentaires effectuées par un algorithme, en fonction de la taille n des données, indépendamment de la vitesse réelle de la machine qui l'exécute.

Le piège classique

Confondre complexité en temps (nombre d'opérations) et complexité en espace (mémoire supplémentaire utilisée) : un algorithme peut être rapide mais gourmand en mémoire, ou l'inverse.

L'astuce

Boucles l'une APRÈS l'autre → on ADDITIONNE les coûts ; boucles l'une DANS l'autre (imbriquées) → on MULTIPLIE les coûts.