Livre_silo 30 août 2013 16:32 Page 146
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
146
Informatique pour tous
Le cas particulier des boucles imbriquées illustre bien le principe de calcul du coût de la
boucle for. Ainsi, si les deux boucles sont répétées respectivement m et m
′ fois, alors le
corps de la boucle interne est exécuté m × m
′ fois en tout. Il est en effet répété à cause de
cette boucle interne, mais aussi parce qu’elle-même est répétée dans son intégralité.
Exercice 6.1 Reprendre les programmes de l’exercice 4.31 et évaluer leur coût.
L’opération de base ici consiste à afficher une étoile à l’écran (ce qu’on peut assimiler à une affectation
qui modifie l’état de la carte graphique au lieu de l’état de la mémoire).
Dans le premier programme, les nombres d’itérations des boucles interne et externe sont indépendants
et ils sont respectivement de p et n. Au total, on effectue n × p affichages dans ce programme, ce qu’on
peut voir dans le résultat produit à l’écran.
Dans le second programme, la boucle interne dépend du compteur de la boucle externe. Le nombre
d’affichages effectués est donc :
n−1 ∑
i=0
(i + 1) =
n(n+1)
2
.
Pour être complet, il faudrait comptabiliser également l’affichage des retours chariot ; ils sont cependant
nettement moins nombreux que les étoiles et ne jouent pas un rôle significatif dans le temps d’exécution
du programme.
POUR ALLER PLUS LOIN Les limites de ce modèle de complexité
Le modèle de complexité qu’on a donné, comme tout modèle, n’est qu’un reflet imparfait
de la réalité. Il n’est évidemment utile que dans les cas où il est suffisamment proche de la
réalité.
Malheureusement, dans certains cas, les hypothèses sous-jacentes à ce modèle ne tiennent
pas. Ainsi, les entiers n’étant pas bornés, il est irréaliste de penser qu’une opération arithmétique ait un coût unitaire : par exemple, l’addition de deux nombres entiers à n chiffres
nécessite de lire tous leurs chiffres et d’écrire ceux du résultat et demande donc un temps de
calcul proportionnel à n. Le temps de calcul d’une opération sur des entiers longs n’est pas
une bonne unité de mesure, puisqu’il peut lui-même dépendre de la taille des opérandes.
Dans cet ouvrage, sauf mention expresse du contraire, on restera sur le modèle précédemment proposé, d’une part parce qu’il convient bien à une large classe de problèmes et
d’autre part parce que le compliquer dépasserait le cadre du programme de cet enseignement.
6.1.2 Complexité et notation O
Dans l’exemple précédent, on a évalué de façon relativement fine le nombre des opérations
effectuées par chacun des algorithmes, par exemple « n comparaisons » ou « entre
√
n et
2
√
n comparaisons ». En réalité, lorsqu’on cherche à évaluer l’efficacité d’un algorithme,
il est souvent inutile d’aller jusqu’à ce niveau de détail : on se contentera de dire que le
nombre d’opérations élémentaires effectuées est par exemple proportionnel à n ou à
√
n.
Il y a plusieurs raisons à cela. D’une part, les différentes opérations élémentaires considérées ne demandent pas toutes exactement le même temps de calcul et cachent donc un
facteur multiplicatif, borné mais très compliqué à déterminer précisément. D’autre part, le
même programme peut être exécuté sur deux machines différentes, l’une étant par exemple
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
146
Informatique pour tous
Le cas particulier des boucles imbriquées illustre bien le principe de calcul du coût de la
boucle for. Ainsi, si les deux boucles sont répétées respectivement m et m
′ fois, alors le
corps de la boucle interne est exécuté m × m
′ fois en tout. Il est en effet répété à cause de
cette boucle interne, mais aussi parce qu’elle-même est répétée dans son intégralité.
Exercice 6.1 Reprendre les programmes de l’exercice 4.31 et évaluer leur coût.
L’opération de base ici consiste à afficher une étoile à l’écran (ce qu’on peut assimiler à une affectation
qui modifie l’état de la carte graphique au lieu de l’état de la mémoire).
Dans le premier programme, les nombres d’itérations des boucles interne et externe sont indépendants
et ils sont respectivement de p et n. Au total, on effectue n × p affichages dans ce programme, ce qu’on
peut voir dans le résultat produit à l’écran.
Dans le second programme, la boucle interne dépend du compteur de la boucle externe. Le nombre
d’affichages effectués est donc :
n−1 ∑
i=0
(i + 1) =
n(n+1)
2
.
Pour être complet, il faudrait comptabiliser également l’affichage des retours chariot ; ils sont cependant
nettement moins nombreux que les étoiles et ne jouent pas un rôle significatif dans le temps d’exécution
du programme.
POUR ALLER PLUS LOIN Les limites de ce modèle de complexité
Le modèle de complexité qu’on a donné, comme tout modèle, n’est qu’un reflet imparfait
de la réalité. Il n’est évidemment utile que dans les cas où il est suffisamment proche de la
réalité.
Malheureusement, dans certains cas, les hypothèses sous-jacentes à ce modèle ne tiennent
pas. Ainsi, les entiers n’étant pas bornés, il est irréaliste de penser qu’une opération arithmétique ait un coût unitaire : par exemple, l’addition de deux nombres entiers à n chiffres
nécessite de lire tous leurs chiffres et d’écrire ceux du résultat et demande donc un temps de
calcul proportionnel à n. Le temps de calcul d’une opération sur des entiers longs n’est pas
une bonne unité de mesure, puisqu’il peut lui-même dépendre de la taille des opérandes.
Dans cet ouvrage, sauf mention expresse du contraire, on restera sur le modèle précédemment proposé, d’une part parce qu’il convient bien à une large classe de problèmes et
d’autre part parce que le compliquer dépasserait le cadre du programme de cet enseignement.
6.1.2 Complexité et notation O
Dans l’exemple précédent, on a évalué de façon relativement fine le nombre des opérations
effectuées par chacun des algorithmes, par exemple « n comparaisons » ou « entre
√
n et
2
√
n comparaisons ». En réalité, lorsqu’on cherche à évaluer l’efficacité d’un algorithme,
il est souvent inutile d’aller jusqu’à ce niveau de détail : on se contentera de dire que le
nombre d’opérations élémentaires effectuées est par exemple proportionnel à n ou à
√
n.
Il y a plusieurs raisons à cela. D’une part, les différentes opérations élémentaires considérées ne demandent pas toutes exactement le même temps de calcul et cachent donc un
facteur multiplicatif, borné mais très compliqué à déterminer précisément. D’autre part, le
même programme peut être exécuté sur deux machines différentes, l’une étant par exemple