Livre_silo 30 août 2013 16:32 Page 145
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
145
6 – Notions de complexité et algorithmique sur les tableaux
en fonction du nombre d’éléments de ce tableau. Une autre possibilité pour la taille du problème est de considérer la taille de la représentation des données passées à ce programme.
Par exemple, pour un programme traitant un texte, on prend pour taille du problème le
nombre de caractères de ce texte.
ATTENTION Taille d’un entier
Lorsqu’un problème dépend d’un paramètre considéré n, il y a deux choix naturels pour la
taille du problème : l’entier lui-même ou la taille des données nécessaires à sa représentation, c’est-à-dire son nombre de chiffres. Dans le problème précédent, si n est l’entier dont
on cherche les diviseurs, il est nécessaire d’effectuer n ou
√
n calculs de restes. S’il s’agit
en revanche de la taille de l’entier dont on cherche les diviseurs, cela signifie que l’entier
considéré possède n chiffres, donc qu’il est compris entre 10 n−1 et 10 n . Il est donc nécessaire d’effectuer entre 10 n−1 et 10 n calculs de restes dans le premier cas et d’en effectuer
entre 10
n−1
2
et 10
n
2 dans le second.
L’évaluation du temps mis par un algorithme pour s’exécuter est un domaine de recherche
à part entière, car elle se révèle parfois très difficile. Néanmoins, dans de nombreux cas,
cette évaluation peut se faire en appliquant quelques règles simples.
SAVOIR-FAIRE Déterminer le coût d’un algorithme
Pour déterminer le coût d’un algorithme, on se fonde en général sur le modèle de
complexité suivant :
• Une affectation, une comparaison ou l’évaluation d’une opération arithmétique
ayant en général un faible temps d’exécution, celui-ci sera considéré comme l’unité
de mesure du coût d’un algorithme.
• Le coût des instructions p et q en séquence est la somme des coûts de l’instruction p
et de l’instruction q.
• Le coût d’un test if b: p else: q est inférieur ou égal au maximum des coûts des
instructions p et q, plus le temps d’évaluation de l’expression b.
• Le coût d’une boucle for i in iterable : p est égal au nombre d’éléments de l’itérable multiplié par le coût de l’instruction p si ce dernier ne dépend pas de la valeur
de i. Quand le coût du corps de la boucle dépend de la valeur de i, le coût total de
la boucle est la somme des coûts du corps de la boucle pour chaque valeur de i.
• Le cas des boucles while est plus complexe à traiter puisque le nombre de répétitions n’ est en général pas connu a priori. On peut majorer le nombre de répétitions
de la boucle de la même façon qu’ on démontre sa terminaison (voir Savoir-faire
Démontrer qu’une boucle se termine p. 101) et ainsi majorer le coût de l’exécution de
la boucle.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
145
6 – Notions de complexité et algorithmique sur les tableaux
en fonction du nombre d’éléments de ce tableau. Une autre possibilité pour la taille du problème est de considérer la taille de la représentation des données passées à ce programme.
Par exemple, pour un programme traitant un texte, on prend pour taille du problème le
nombre de caractères de ce texte.
ATTENTION Taille d’un entier
Lorsqu’un problème dépend d’un paramètre considéré n, il y a deux choix naturels pour la
taille du problème : l’entier lui-même ou la taille des données nécessaires à sa représentation, c’est-à-dire son nombre de chiffres. Dans le problème précédent, si n est l’entier dont
on cherche les diviseurs, il est nécessaire d’effectuer n ou
√
n calculs de restes. S’il s’agit
en revanche de la taille de l’entier dont on cherche les diviseurs, cela signifie que l’entier
considéré possède n chiffres, donc qu’il est compris entre 10 n−1 et 10 n . Il est donc nécessaire d’effectuer entre 10 n−1 et 10 n calculs de restes dans le premier cas et d’en effectuer
entre 10
n−1
2
et 10
n
2 dans le second.
L’évaluation du temps mis par un algorithme pour s’exécuter est un domaine de recherche
à part entière, car elle se révèle parfois très difficile. Néanmoins, dans de nombreux cas,
cette évaluation peut se faire en appliquant quelques règles simples.
SAVOIR-FAIRE Déterminer le coût d’un algorithme
Pour déterminer le coût d’un algorithme, on se fonde en général sur le modèle de
complexité suivant :
• Une affectation, une comparaison ou l’évaluation d’une opération arithmétique
ayant en général un faible temps d’exécution, celui-ci sera considéré comme l’unité
de mesure du coût d’un algorithme.
• Le coût des instructions p et q en séquence est la somme des coûts de l’instruction p
et de l’instruction q.
• Le coût d’un test if b: p else: q est inférieur ou égal au maximum des coûts des
instructions p et q, plus le temps d’évaluation de l’expression b.
• Le coût d’une boucle for i in iterable : p est égal au nombre d’éléments de l’itérable multiplié par le coût de l’instruction p si ce dernier ne dépend pas de la valeur
de i. Quand le coût du corps de la boucle dépend de la valeur de i, le coût total de
la boucle est la somme des coûts du corps de la boucle pour chaque valeur de i.
• Le cas des boucles while est plus complexe à traiter puisque le nombre de répétitions n’ est en général pas connu a priori. On peut majorer le nombre de répétitions
de la boucle de la même façon qu’ on démontre sa terminaison (voir Savoir-faire
Démontrer qu’une boucle se termine p. 101) et ainsi majorer le coût de l’exécution de
la boucle.