Performances

Le temps d'exécution d'un programme peut être mesuré expérimentalement. Sous Unix, la commande time affiche plusieurs estimations de ce temps, en secondes ; par exemple, un programme euclide est exécuté et son temps d'exécution est évalué en soumettant la commande suivante au shell :

unix% time euclide
13.240u 0.870s 0:19.30 73.1% 0+853k 0+16io 0pf+0w

• le premier nombre (suffixé par u, pour user) est le temps d'exécution des instructions du programme ;
• le second (suffixé par s, pour system) est le temps d'exécution d'instructions du système nécessaires à l'exécution du programme, mais qui ne figurent pas dans le programme ;
• le troisième est le temps écoulé entre le début et la fin de l'exécution du programme ; ce temps pourrait être mesuré par un utilisateur muni d'un chronomètre ; il dépend non seulement du programme, mais aussi de la charge du système, notamment des autres programmes en cours d'exécution, et des temps d'entrée-sortie ;
• le suivant est le pourcentage du temps consacré au programme, c'est-à-dire $\mathtt{u} + \mathtt{s}$ rapporté au temps écoulé ;
• les trois derniers nombres sont des évaluations des accès à la mémoire (espace utilisé, entrées-sorties, pages).

Il est important d'être capable d'évaluer a priori ce temps u, sans devoir exécuter le programme. Si l'on dispose d'information sur la machine, on a l'estimation suivante :

$$\begin{eqnarray*} \mbox{temps d'exécution} &= &\mbox{nombre d'instructions du pr... ...es/instruction} \\ &&\times\ \mbox{durée d'un cycle d'horloge} \end{eqnarray*}$$

Le programmeur peut seulement agir sur le nombre d'instructions ; les deux autres facteurs de cette formule sont respectivement du ressort de l'architecte de la machine et de l'électronicien. Bien que les instructions mentionnées dans cette formule ne soient pas celles du langage source, mais celles de la machine, une évaluation du temps d'exécution peut être obtenue en analysant le programme-source.

L'usage est de dénombrer certaines instructions significatives : nombre d'opérations arithmétiques dans un algorithme numérique, nombre d'itérations ou d'appels récursifs, nombre de comparaisons dans un algorithme de recherche d'un élément dans une table. Cette évaluation se fait en fonction d'une grandeur caractéristique du problème : valeur d'une donnée, taille d'un tableau, profondeur d'un arbre, etc. Plutôt que de temps d'exécution, on parlera d'une mesure de complexité.

En outre, il s'agit souvent de comparer plusieurs algorithmes entre eux, indépendamment des machines auxquelles ils sont destinés. On s'intéresse donc surtout à l'ordre de grandeur d'une mesure de complexité, c'est-à-dire à des estimations asymptotiques. On rencontrera notamment des algorithmes linéaires quand la complexité est en $\Theta(n)$, logarithmiques, en $\Theta(\log n)$, quadratiques, en $\Theta(n^2)$, etc. Rappelons que $\Theta(f)$ est l'ensemble des fonctions $g$ pour lesquelles il existe des entiers $N$, $a$ et $b$ positifs tels que $a f(n) \le g(n) \le b f(n)$ pour tout $n\ge N$.