“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 156 — #166
i
i
i
i
i
i
i
i
156
3
• Techniques de programmation déclarative
proportionnel à n. C’est parce que l’arité est stockée une fois dans une table de
symboles. Pour chaque procédure distincte dans le code source, le coût additionnel
dépend de la taille du code machine, qui est approximativement proportionnelle au
nombre total d’instructions et d’identificateurs dans le corps de la procédure. Dans la
plupart des cas, ces coûts supplémentaires ajoutent une constante à la consommation
totale de mémoire ; pour le calcul on peut généralement les ignorer.
3.6.3 La complexité amortie
Il arrive parfois qu’une opération ait une complexité trop élevée mais qu’une série
d’opérations ait une complexité acceptable. Par exemple, on peut implémenter les files
ainsi. Une opération individuelle d’insertion ou de retrait a une complexité O(n), ce
qui est trop cher, mais une série de n opérations a aussi une complexité de O(n), ce
qui est acceptable. En fait la plupart des opérations sont O(1) mais de temps en temps
il y a une opération O(n). Comme les opérations chères sont peu fréquentes, elles
n’augmentent pas la complexité de la série. En général, si une série de n opérations
a une temps d’exécution O( f (n)), nous disons qu’une opération individuelle a une
complexité amortie O( f (n)/n).
La complexité amortie versus la complexité au pire
Dans la plupart des domaines d’application, il suffit d’avoir une complexité amortie
acceptable. Mais il y a trois domaines qui ont besoin de garanties sur le temps d’exécution des opérations individuelles. Ce sont les systèmes temps réel dur, les systèmes
parallèles et les systèmes interactifs à haute performance.
Un système temps réel dur doit satisfaire des échéances strictes sur la terminaison
des calculs. Manquer une telle échéance peut avoir des conséquences graves, y compris
des pertes humaines. De tels systèmes existent, par exemple les stimulateurs cardiaques
et les dispositifs de sécurité ferroviaires (pour éviter les collisions des trains).
Un système parallèle exécute plusieurs calculs simultanément pour augmenter
la vitesse du calcul global. Souvent le calcul global ne peut avancer qu’après la
terminaison de tous les calculs simultanés. Si un de ces calculs prend plus de temps, il
fera ralentir le calcul global.
Un système interactif, comme un jeu sur ordinateur, doit avoir un temps de réaction
qui ne varie pas trop. Par exemple, si un jeu multijoueur a une réaction retardée pour
un des joueurs, la satisfaction de ce joueur sera de beaucoup réduite.
La méthode du banquier et la méthode du physicien
Le calcul de la complexité amortie est un peu plus difficile que le calcul de la complexité au pire. Il y a essentiellement deux méthodes, appelées la méthode du banquier
et la méthode du physicien.
i
i
i
i
i
i
i
i
156
3
• Techniques de programmation déclarative
proportionnel à n. C’est parce que l’arité est stockée une fois dans une table de
symboles. Pour chaque procédure distincte dans le code source, le coût additionnel
dépend de la taille du code machine, qui est approximativement proportionnelle au
nombre total d’instructions et d’identificateurs dans le corps de la procédure. Dans la
plupart des cas, ces coûts supplémentaires ajoutent une constante à la consommation
totale de mémoire ; pour le calcul on peut généralement les ignorer.
3.6.3 La complexité amortie
Il arrive parfois qu’une opération ait une complexité trop élevée mais qu’une série
d’opérations ait une complexité acceptable. Par exemple, on peut implémenter les files
ainsi. Une opération individuelle d’insertion ou de retrait a une complexité O(n), ce
qui est trop cher, mais une série de n opérations a aussi une complexité de O(n), ce
qui est acceptable. En fait la plupart des opérations sont O(1) mais de temps en temps
il y a une opération O(n). Comme les opérations chères sont peu fréquentes, elles
n’augmentent pas la complexité de la série. En général, si une série de n opérations
a une temps d’exécution O( f (n)), nous disons qu’une opération individuelle a une
complexité amortie O( f (n)/n).
La complexité amortie versus la complexité au pire
Dans la plupart des domaines d’application, il suffit d’avoir une complexité amortie
acceptable. Mais il y a trois domaines qui ont besoin de garanties sur le temps d’exécution des opérations individuelles. Ce sont les systèmes temps réel dur, les systèmes
parallèles et les systèmes interactifs à haute performance.
Un système temps réel dur doit satisfaire des échéances strictes sur la terminaison
des calculs. Manquer une telle échéance peut avoir des conséquences graves, y compris
des pertes humaines. De tels systèmes existent, par exemple les stimulateurs cardiaques
et les dispositifs de sécurité ferroviaires (pour éviter les collisions des trains).
Un système parallèle exécute plusieurs calculs simultanément pour augmenter
la vitesse du calcul global. Souvent le calcul global ne peut avancer qu’après la
terminaison de tous les calculs simultanés. Si un de ces calculs prend plus de temps, il
fera ralentir le calcul global.
Un système interactif, comme un jeu sur ordinateur, doit avoir un temps de réaction
qui ne varie pas trop. Par exemple, si un jeu multijoueur a une réaction retardée pour
un des joueurs, la satisfaction de ce joueur sera de beaucoup réduite.
La méthode du banquier et la méthode du physicien
Le calcul de la complexité amortie est un peu plus difficile que le calcul de la complexité au pire. Il y a essentiellement deux méthodes, appelées la méthode du banquier
et la méthode du physicien.