Livre_silo 30 août 2013 16:32 Page 150
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
150
Informatique pour tous
En revanche, dans le pire cas, la batterie du téléphone est déchargée, il convient donc de
la recharger pendant 4 heures. Le coût dans le pire cas pour un envoi est donc de 4 heures
et 2 minutes.
Néanmoins, le coût pour n envois, où n est grand, est bien inférieur à 4n heures et 2n minutes. En effet, une fois le téléphone chargé, son utilisateur va pouvoir envoyer un millier
de SMS avant de devoir recharger la batterie. On peut donc dire que dans le pire cas, l’envoi
de n SMS successifs va demander
⌈
n
1 000
⌉
× 4 heures plus 2n minutes, On a donc la garantie
que pour n grand, le temps mis pour envoyer n SMS est au plus de l’ordre de n × 14 secondes plus 2n minutes. Autrement dit, le temps mis pour envoyer un SMS est de l’ordre de
2 minutes et 14 secondes. On dit que cette durée est la complexité amortie représentant le
coût de l’envoi. La notion d’amortissement vient de la comptabilité : le coût d’un kilomètre
en voiture est nul si la voiture fonctionne et si le plein est fait, alors qu’il est extrêmement
élevé s’il faut commencer par acheter la voiture. La notion pertinente pour mesurer ce coût
est en général de calculer l’amortissement des dépenses initiales (l’achat de la voiture) sur
la totalité du kilométrage.
C’est une situation qu’on retrouve en informatique : il arrive ainsi que, dans certains problèmes, une opération ait un coût O(n) dans le pire cas, où n est la taille du problème, et un
coût constant en complexité amortie. En Python, l’opération d’ajout d’un nouvel élément
à la fin d’un tableau de taille n rentre dans ce cadre.
Cependant, la théorie de la complexité amortie dépasse le cadre de cet ouvrage.
Exercice 6.3 Quelle est la complexité en temps d’un algorithme de division euclidienne procédant par
soustractions successives ? Et sa complexité en espace ?
Comparer avec la complexité en temps et en espace de l’algorithme de division euclidienne que l’on
apprend à l’école primaire et au collège (on ne cherchera pas à le programmer).
Exercice 6.4 Quelle est la complexité en temps de l’algorithme écrit dans l’exercice 4.36 ?
Exercice 6.5 * Quelle est la complexité en temps de la version récursive de l’algorithme de Horner présentée page 154 ?
Et sa complexité en espace ?
6.2 Structure de tableau
6.2.1 Construction d’un tableau
De manière simple, un tableau ² n’est rien d’autre qu’une suite de valeurs stockées dans des
cases mémoire contiguës. Ainsi, on représentera graphiquement le tableau contenant la
suite de valeurs entières 3, 7, 42, 1, 4, 8, 12 de la manière suivante :
3
7
42
1
4
8
12
La particularité d’une structure de tableau est que le contenu de la i-ème case peut être lu
ou modifié en temps constant, c’est-à-dire indépendant de i.
2. Dans la terminologie Python, la structure de données correspondante est appelée une « liste », ce qui est
un peu malheureux. Nous donnerons un peu plus de détails sur cette structure dans le chapitre 12.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
150
Informatique pour tous
En revanche, dans le pire cas, la batterie du téléphone est déchargée, il convient donc de
la recharger pendant 4 heures. Le coût dans le pire cas pour un envoi est donc de 4 heures
et 2 minutes.
Néanmoins, le coût pour n envois, où n est grand, est bien inférieur à 4n heures et 2n minutes. En effet, une fois le téléphone chargé, son utilisateur va pouvoir envoyer un millier
de SMS avant de devoir recharger la batterie. On peut donc dire que dans le pire cas, l’envoi
de n SMS successifs va demander
⌈
n
1 000
⌉
× 4 heures plus 2n minutes, On a donc la garantie
que pour n grand, le temps mis pour envoyer n SMS est au plus de l’ordre de n × 14 secondes plus 2n minutes. Autrement dit, le temps mis pour envoyer un SMS est de l’ordre de
2 minutes et 14 secondes. On dit que cette durée est la complexité amortie représentant le
coût de l’envoi. La notion d’amortissement vient de la comptabilité : le coût d’un kilomètre
en voiture est nul si la voiture fonctionne et si le plein est fait, alors qu’il est extrêmement
élevé s’il faut commencer par acheter la voiture. La notion pertinente pour mesurer ce coût
est en général de calculer l’amortissement des dépenses initiales (l’achat de la voiture) sur
la totalité du kilométrage.
C’est une situation qu’on retrouve en informatique : il arrive ainsi que, dans certains problèmes, une opération ait un coût O(n) dans le pire cas, où n est la taille du problème, et un
coût constant en complexité amortie. En Python, l’opération d’ajout d’un nouvel élément
à la fin d’un tableau de taille n rentre dans ce cadre.
Cependant, la théorie de la complexité amortie dépasse le cadre de cet ouvrage.
Exercice 6.3 Quelle est la complexité en temps d’un algorithme de division euclidienne procédant par
soustractions successives ? Et sa complexité en espace ?
Comparer avec la complexité en temps et en espace de l’algorithme de division euclidienne que l’on
apprend à l’école primaire et au collège (on ne cherchera pas à le programmer).
Exercice 6.4 Quelle est la complexité en temps de l’algorithme écrit dans l’exercice 4.36 ?
Exercice 6.5 * Quelle est la complexité en temps de la version récursive de l’algorithme de Horner présentée page 154 ?
Et sa complexité en espace ?
6.2 Structure de tableau
6.2.1 Construction d’un tableau
De manière simple, un tableau ² n’est rien d’autre qu’une suite de valeurs stockées dans des
cases mémoire contiguës. Ainsi, on représentera graphiquement le tableau contenant la
suite de valeurs entières 3, 7, 42, 1, 4, 8, 12 de la manière suivante :
3
7
42
1
4
8
12
La particularité d’une structure de tableau est que le contenu de la i-ème case peut être lu
ou modifié en temps constant, c’est-à-dire indépendant de i.
2. Dans la terminologie Python, la structure de données correspondante est appelée une « liste », ce qui est
un peu malheureux. Nous donnerons un peu plus de détails sur cette structure dans le chapitre 12.