next up previous contents index
suivant: Définitions récursives monter: main précédent: Itération while   Table des matières   Index


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

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$.


next up previous contents index
suivant: Définitions récursives monter: main précédent: Itération while   Table des matières   Index
R Lalement