“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 148 — #158
i
i
i
i
i
i
i
i
148
3
• Techniques de programmation déclarative
l’utilisation de mémoire (par exemple, en octets). Nous montrons comment calculer
les deux.
3.6.1 Le temps d’exécution
En utilisant le langage noyau et sa sémantique, nous pouvons calculer le temps d’exécution à un facteur constant près. Par exemple, pour un algorithme de tri par fusion
nous pouvons dire que le temps d’exécution est proportionnel à n log n, avec une liste
d’entrée de longueur n. La complexité asymptotique en temps d’un algorithme est
la meilleure borne supérieure de son temps d’exécution en fonction de la taille de
l’entrée, à un facteur constant près. Cette borne est aussi appelée la complexité en
temps dans le pire cas.
Pour trouver le facteur constant, il est nécessaire de mesurer l’exécution du programme. Calculer le facteur constant sans exécuter le programme est extrêmement
difficile. C’est parce que les ordinateurs modernes ont une structure logicielle et matérielle complexe qui introduit beaucoup d’imprévisibilité dans le temps d’exécution :
ils font de la gestion de mémoire (voir section 2.5), ils ont des systèmes de mémoire
complexes (avec la mémoire virtuelle et plusieurs niveaux de mémoire cache), ils ont
une architecture pipeline et super-scalaire (plusieurs instructions s’exécutent simultanément ; le temps d’exécution d’une instruction dépend souvent des autres instructions
présentes) et le système d’exploitation fait des changements de contexte à des moments
imprévisibles. Cette imprévisibilité améliore la performance moyenne au prix d’une
augmentation de sa variabilité. Pour plus d’informations sur les mesures de performance et ses dangers, nous recommandons [43].
La notation grand O
Nous donnons le temps d’exécution du programme avec la notation « grand O ». Cette
notation nous permet de parler du temps d’exécution sans avoir à préciser le facteur
constant. Soit T (n) une fonction qui donne le temps d’exécution d’un programme,
mesuré en fonction de la taille de l’entrée n. Soit f (n) une autre fonction définie
sur les entiers non négatifs. Nous disons alors que T (n) est de l’ordre de f (n), noté
O( f (n)), si T (n) c · f (n) pour une constante positive c, pour tout n sauf certaines
petites valeurs n n 0 . En d’autres termes, quand n grandit il y a un point n 0 au-delà
duquel T (n) ne devient jamais plus grand que c · f (n).
Parfois on écrit T (n) = O( f (n)), avec une égalité « = ». Attention ! Cette utilisation de l’égalité est un abus de notation, parce qu’il n’y a pas d’égalité. Si g(n)
= O( f (n)) et h(n) = O( f (n)), il n’est pas vrai que g(n) = h(n). Une meilleure
manière de comprendre la notation grand O est avec les ensembles et leurs membres :
O( f (n)) est un ensemble de fonctions et T (n) = O( f (n)) veut simplement dire que
T (n) est un membre de l’ensemble.
i
i
i
i
i
i
i
i
148
3
• Techniques de programmation déclarative
l’utilisation de mémoire (par exemple, en octets). Nous montrons comment calculer
les deux.
3.6.1 Le temps d’exécution
En utilisant le langage noyau et sa sémantique, nous pouvons calculer le temps d’exécution à un facteur constant près. Par exemple, pour un algorithme de tri par fusion
nous pouvons dire que le temps d’exécution est proportionnel à n log n, avec une liste
d’entrée de longueur n. La complexité asymptotique en temps d’un algorithme est
la meilleure borne supérieure de son temps d’exécution en fonction de la taille de
l’entrée, à un facteur constant près. Cette borne est aussi appelée la complexité en
temps dans le pire cas.
Pour trouver le facteur constant, il est nécessaire de mesurer l’exécution du programme. Calculer le facteur constant sans exécuter le programme est extrêmement
difficile. C’est parce que les ordinateurs modernes ont une structure logicielle et matérielle complexe qui introduit beaucoup d’imprévisibilité dans le temps d’exécution :
ils font de la gestion de mémoire (voir section 2.5), ils ont des systèmes de mémoire
complexes (avec la mémoire virtuelle et plusieurs niveaux de mémoire cache), ils ont
une architecture pipeline et super-scalaire (plusieurs instructions s’exécutent simultanément ; le temps d’exécution d’une instruction dépend souvent des autres instructions
présentes) et le système d’exploitation fait des changements de contexte à des moments
imprévisibles. Cette imprévisibilité améliore la performance moyenne au prix d’une
augmentation de sa variabilité. Pour plus d’informations sur les mesures de performance et ses dangers, nous recommandons [43].
La notation grand O
Nous donnons le temps d’exécution du programme avec la notation « grand O ». Cette
notation nous permet de parler du temps d’exécution sans avoir à préciser le facteur
constant. Soit T (n) une fonction qui donne le temps d’exécution d’un programme,
mesuré en fonction de la taille de l’entrée n. Soit f (n) une autre fonction définie
sur les entiers non négatifs. Nous disons alors que T (n) est de l’ordre de f (n), noté
O( f (n)), si T (n) c · f (n) pour une constante positive c, pour tout n sauf certaines
petites valeurs n n 0 . En d’autres termes, quand n grandit il y a un point n 0 au-delà
duquel T (n) ne devient jamais plus grand que c · f (n).
Parfois on écrit T (n) = O( f (n)), avec une égalité « = ». Attention ! Cette utilisation de l’égalité est un abus de notation, parce qu’il n’y a pas d’égalité. Si g(n)
= O( f (n)) et h(n) = O( f (n)), il n’est pas vrai que g(n) = h(n). Une meilleure
manière de comprendre la notation grand O est avec les ensembles et leurs membres :
O( f (n)) est un ensemble de fonctions et T (n) = O( f (n)) veut simplement dire que
T (n) est un membre de l’ensemble.