La description de chaque opération doit donner une indication de sa
performance, concernant en particulier le temps de calcul, mais aussi
la consommation de mémoire. Ces descriptions peuvent
éventuellement être omises s'il est clair que l'opération est
efficace. En particulier, si l'opération appartient à un type
abstrait bien connu et que son comportement est bien connu aussi, il
n'est pas nécessaire d'inclure ces descriptions. Un exemple est
l'opération pour enfiler un objet dans une file. Si le type abstrait
est bien programmé, cette opération doit être exécutée en avec
très peu d'instructions et ne doit pas allouer beaucoup de mémoire.
Par contre, pour les types abstraits moins connus ou les types abstraits spécifiques à l'application, il est important de documenter la performance.
La description d'une opération doit contenir un indication de la complexité asymptotique au pire. Cette information est importante pour le programmeur consommateur afin qu'il puisse estimer le temps de calcul de l'application dans le pire des cas.
Mais la complexité asymptotique ne suffit pas à décrire la
performance. D'abord, il est utile d'inclure une indication
concernant la constante multiplicative de la complexité. Ensuite, il n'est
pas sûr que les cas les pire arrivent souvent en
pratique. C'est le cas en particulier de certains algorithmes comme
le tri rapide dont la complexité asymptotique est mais
qui est très rapide en pratique et la méthode du simplexe qui est
exponentielle au pire, mais qui est pourtant l'algorithme le plus
rapide qui fonctionne pour la programmation linéaire. C'est aussi le cas quand
la performance dépend d'un motif d'utilisation. La gestion du
tampon de l'éditeur Emacs est par exemple relativement coûteuse si
l'on regarde la complexité asymptotique. Mais pour toute utilisation
normale, elle est très rapide.
Par conséquent, il est utile d'indiquer dans la description d'une opération tous les aspects de la performance, afin d'assister le programmeur consommateur dans son choix.
Irene DURAND