Livre_silo 30 août 2013 16:32 Page 144
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
144
Informatique pour tous
6.1 Complexité d’un algorithme
6.1.1 Plusieurs algorithmes pour un même problème
Pour traiter un même problème, il existe souvent plusieurs algorithmes. Quand on doit
choisir, l’un des critères est celui du temps d’exécution, qu’on appelle aussi parfois coût de
l’algorithme. Cette dénomination n’est pas usurpée car ce temps conditionne les ressources
utilisées (machine sur laquelle on exécutera l’algorithme, consommation électrique…).
Pour un logiciel interactif, par exemple, un temps de réponse court est un élément essentiel
du confort de l’utilisateur. De même, certains programmes industriels doivent être utilisés
un grand nombre de fois dans un délai très court et même un programme qui n’est exécuté
qu’une seule fois, par exemple un programme de simulation écrit pour tester une hypothèse
de recherche, est inutilisable s’il demande des mois ou des années de calcul.
Par exemple, si l’on cherche à afficher la liste des diviseurs d’un nombre entier n, on peut
écrire l’algorithme naïf suivant :
def diviseurs(n):
for i in range(1,n+1):
if n % i == 0:
print(i)
Cet algorithme réalise exactement n calculs de restes de divisions euclidiennes, n comparaisons et au plus n affichages. Cependant, on peut aussi utiliser le fait que si n = p × q
avec p ⩾
√
n, alors q est un diviseur de n inférieur ou égal à
√
n. Il suffit donc de chercher
chaque diviseur q inférieur ou égal à
√
n et de calculer p = n/q pour obtenir tous les
diviseurs. Dans le cas où n est un carré parfait, on prend soin de ne pas afficher sa racine
carrée deux fois :
import math
def diviseurs(n):
for i in range(1,int(math.sqrt(n))+1):
if n % i == 0:
print(i)
if n//i != i:
print(n//i)
Ce deuxième algorithme ne fait plus que ⌊
√
n⌋ itérations, qui effectuent chacune un calcul
de reste, une ou deux comparaisons, et zéro, un ou deux affichage(s). Au total, il coûte donc
un calcul de racine carrée, ⌊
√
n⌋ calculs de reste, entre ⌊
√
n⌋ et 2 ⌊
√
n⌋ comparaisons et
entre 0 et 2⌊
√
n⌋ affichages.
En général, on cherche à déterminer comment le temps d’exécution d’un algorithme varie
en fonction d’un paramètre qu’ on appelle la taille du problème. Le temps de recherche des
diviseurs d’un entier n dépend de n, qu’on pourra donc naturellement prendre comme taille
du problème. Comme on l’a vu, selon l’algorithme, ce temps peut être proportionnel à n ou
à
√
n. De même, quand on s’interrogera sur l’efficacité d’un algorithme manipulant des tableaux, on cherchera à comprendre comment le temps d’exécution de cet algorithme varie
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
144
Informatique pour tous
6.1 Complexité d’un algorithme
6.1.1 Plusieurs algorithmes pour un même problème
Pour traiter un même problème, il existe souvent plusieurs algorithmes. Quand on doit
choisir, l’un des critères est celui du temps d’exécution, qu’on appelle aussi parfois coût de
l’algorithme. Cette dénomination n’est pas usurpée car ce temps conditionne les ressources
utilisées (machine sur laquelle on exécutera l’algorithme, consommation électrique…).
Pour un logiciel interactif, par exemple, un temps de réponse court est un élément essentiel
du confort de l’utilisateur. De même, certains programmes industriels doivent être utilisés
un grand nombre de fois dans un délai très court et même un programme qui n’est exécuté
qu’une seule fois, par exemple un programme de simulation écrit pour tester une hypothèse
de recherche, est inutilisable s’il demande des mois ou des années de calcul.
Par exemple, si l’on cherche à afficher la liste des diviseurs d’un nombre entier n, on peut
écrire l’algorithme naïf suivant :
def diviseurs(n):
for i in range(1,n+1):
if n % i == 0:
print(i)
Cet algorithme réalise exactement n calculs de restes de divisions euclidiennes, n comparaisons et au plus n affichages. Cependant, on peut aussi utiliser le fait que si n = p × q
avec p ⩾
√
n, alors q est un diviseur de n inférieur ou égal à
√
n. Il suffit donc de chercher
chaque diviseur q inférieur ou égal à
√
n et de calculer p = n/q pour obtenir tous les
diviseurs. Dans le cas où n est un carré parfait, on prend soin de ne pas afficher sa racine
carrée deux fois :
import math
def diviseurs(n):
for i in range(1,int(math.sqrt(n))+1):
if n % i == 0:
print(i)
if n//i != i:
print(n//i)
Ce deuxième algorithme ne fait plus que ⌊
√
n⌋ itérations, qui effectuent chacune un calcul
de reste, une ou deux comparaisons, et zéro, un ou deux affichage(s). Au total, il coûte donc
un calcul de racine carrée, ⌊
√
n⌋ calculs de reste, entre ⌊
√
n⌋ et 2 ⌊
√
n⌋ comparaisons et
entre 0 et 2⌊
√
n⌋ affichages.
En général, on cherche à déterminer comment le temps d’exécution d’un algorithme varie
en fonction d’un paramètre qu’ on appelle la taille du problème. Le temps de recherche des
diviseurs d’un entier n dépend de n, qu’on pourra donc naturellement prendre comme taille
du problème. Comme on l’a vu, selon l’algorithme, ce temps peut être proportionnel à n ou
à
√
n. De même, quand on s’interrogera sur l’efficacité d’un algorithme manipulant des tableaux, on cherchera à comprendre comment le temps d’exécution de cet algorithme varie