“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 12 — #22
i
i
i
i
i
i
i
i
12
1
• Introduction aux concepts de programmation
le garder, alors un appel suffirait. Nous pouvons le garder en utilisant une variable
locale. Voici une nouvelle fonction, FastPascal, qui utilise une variable locale :
declare
fun {FastPascal N}
if N==1 then [1] else L in
L={FastPascal N-1}
{AddList {ShiftLeft L} {ShiftRight L}} end
end
Nous déclarons la variable locale L en ajoutant « L in » à la branche else. C’est
comme l’instruction declare, sauf que l’identificateur peut seulement être utilisé
entre le else et le end. Nous lions L au résultat de {FastPascal N-1}. Nous
pouvons ensuite utiliser L partout où nous en avons besoin. Quelle est la vitesse de
FastPascal ? Essayez de calculer la rangée 30. Cela prend des dizaines de secondes
avec Pascal, mais c’est pratiquement instantané avec FastPascal. Une leçon à
tirer de cet exemple est qu’il est plus important d’avoir un bon algorithme que d’avoir
l’ordinateur le plus rapide.
Des garanties sur le temps d’exécution
Comme le montre cet exemple, il est important d’avoir des informations sur le temps
d’exécution d’un programme. Connaître le temps exact est moins important que de
savoir que le temps n’explosera pas avec la taille de l’entrée. Le temps d’exécution d’un
programme en fonction de la taille de l’entrée, à un facteur constant près, s’appelle
la complexité temporelle du programme. La forme de cette fonction dépend de la
façon dont on mesure la taille de l’entrée. Il faut prendre une taille qui a un sens
pour l’utilisation du programme. Par exemple, nous prenons l’entier N comme la taille
de l’entrée de {Pascal N} (et pas, comme on pourrait imaginer, la quantité de
mémoire nécessaire pour stocker l’entier N).
La complexité temporelle de {Pascal N} est proportionnelle à 2
n . C’est une
fonction exponentielle en n, qui augmente rapidement quand n augmente. Quelle
est la complexité temporelle de {FastPascal N} ? Il y a n appels récursifs et
chaque appel prend un temps proportionnel à n. La complexité temporelle est donc
proportionnelle à n
2 . C’est une fonction polynomiale en n, qui augmente beaucoup
plus lentement qu’une fonction exponentielle. Les programmes dont la complexité
temporelle est exponentielle ne sont pas pratiques sauf pour des entrées très petites. En
revanche, les programmes sont pratiques si la complexité temporelle est un polynôme
de petit ordre.
i
i
i
i
i
i
i
i
12
1
• Introduction aux concepts de programmation
le garder, alors un appel suffirait. Nous pouvons le garder en utilisant une variable
locale. Voici une nouvelle fonction, FastPascal, qui utilise une variable locale :
declare
fun {FastPascal N}
if N==1 then [1] else L in
L={FastPascal N-1}
{AddList {ShiftLeft L} {ShiftRight L}} end
end
Nous déclarons la variable locale L en ajoutant « L in » à la branche else. C’est
comme l’instruction declare, sauf que l’identificateur peut seulement être utilisé
entre le else et le end. Nous lions L au résultat de {FastPascal N-1}. Nous
pouvons ensuite utiliser L partout où nous en avons besoin. Quelle est la vitesse de
FastPascal ? Essayez de calculer la rangée 30. Cela prend des dizaines de secondes
avec Pascal, mais c’est pratiquement instantané avec FastPascal. Une leçon à
tirer de cet exemple est qu’il est plus important d’avoir un bon algorithme que d’avoir
l’ordinateur le plus rapide.
Des garanties sur le temps d’exécution
Comme le montre cet exemple, il est important d’avoir des informations sur le temps
d’exécution d’un programme. Connaître le temps exact est moins important que de
savoir que le temps n’explosera pas avec la taille de l’entrée. Le temps d’exécution d’un
programme en fonction de la taille de l’entrée, à un facteur constant près, s’appelle
la complexité temporelle du programme. La forme de cette fonction dépend de la
façon dont on mesure la taille de l’entrée. Il faut prendre une taille qui a un sens
pour l’utilisation du programme. Par exemple, nous prenons l’entier N comme la taille
de l’entrée de {Pascal N} (et pas, comme on pourrait imaginer, la quantité de
mémoire nécessaire pour stocker l’entier N).
La complexité temporelle de {Pascal N} est proportionnelle à 2
n . C’est une
fonction exponentielle en n, qui augmente rapidement quand n augmente. Quelle
est la complexité temporelle de {FastPascal N} ? Il y a n appels récursifs et
chaque appel prend un temps proportionnel à n. La complexité temporelle est donc
proportionnelle à n
2 . C’est une fonction polynomiale en n, qui augmente beaucoup
plus lentement qu’une fonction exponentielle. Les programmes dont la complexité
temporelle est exponentielle ne sont pas pratiques sauf pour des entrées très petites. En
revanche, les programmes sont pratiques si la complexité temporelle est un polynôme
de petit ordre.