Définition · Algorithmique · L1
Complexité en temps
Définition
Le nombre d'opérations élémentaires (comparaisons, affectations, opérations arithmétiques, accès à un tableau) effectuées par un algorithme, exprimé en fonction de la taille de l'entrée. Complexité en espace : la mémoire supplémentaire utilisée.
On ne compte pas des secondes, qui dépendent de la machine : on compte des opérations, et l'on s'intéresse à leur ordre de grandeur quand devient grand.
Cette notion est traitée dans la fiche Complexité des algorithmes et algorithmes de tri, partie « Mesurer la complexité · Ce que l'on mesure », avec ses exceptions, ses exemples, les pièges d'examen et des sujets corrigés en plan.