Mesure de temps d'exécution

Un algorithme prend en entrée une quantité de données que nous noterons en règle générale $n$, par exemple la taille d'un tableau, le nombre d'élément d'une liste chaînée, le nombre de noeuds d'un graphe, etc. Nous considérerons le nombre d'opérations $u_n$ exécuté par l'algorithme et tenterons de classifier $u$ en utilisant une fonction $v$. Ce critère est intéressant pour plusieurs raisons :

• Quelle que soit le temps que mette une machine particulière à exécuter une opération, nous compterons le nombre d'opérations.
• Se limiter au dénombrement des opérations n'est pas suffisant, ce qui nous intéresse vraiment est la façon dont le nombre d'opérations effectuées par l'algorithme croît en fonction du nombre $n$ de données.

Nous considérerons en règle générale le temps d'exécution dans le pire des cas. Quelques bornes asymptotiques supérieures sont à considérer avec un attention particulière :