Livre_silo 30 août 2013 16:32 Page 148
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
148
Informatique pour tous
Tableau 6.1 Ordres de grandeur des temps d’exécution
d’un problème de taille 10 6 sur un ordinateur à un milliard d’opérations par seconde (suite)
O(n k ) polynômiale
30 ans
si k = 3
Ici, n k est le terme de plus haut degré d’un polynôme en n ; il
n’est pas rare de voir des complexités en O(n 3 ) ou O(n 4 ).
O(2 n )
exponentielle plus de 10 300 000
milliards d’années
Un algorithme d’une telle complexité est impraticable sauf
pour de très petites données (n < 50). Comme pour la complexité logarithmique, la base de l’exponentielle ne change
fondamentalement rien à l’inefficacité de l’algorithme.
Exercice 6.2 Les algorithmes suivants calculent et affichent différentes listes de nombres. Quelle est la
complexité de chacun d’entre eux ?
def table1(n):
for i in range(11):
print(i * n)
def table2(n):
for i in range(n):
print(i * i)
def table3(n):
for i in range(n):
for j in range(n):
print(i * j, end=" ")
print()
• L’algorithme table1 affiche la table de multiplication de n jusqu’au rang 10. La boucle est toujours
exécutée 11 fois et ne comporte qu’une multiplication. Le temps d’exécution ne dépend donc pas de
l’entrée n : la complexité est O(1).
• L’algorithme table2 affiche la suite des carrés des nombres entiers jusqu’à (n − 1) 2 . La boucle est
exécutée n fois et ne comporte qu’une multiplication : la complexité est O(n).
• L’algorithme table3 construit une table de multiplication pour tous les entiers de 1 à n en donnant tous
leurs multiples jusqu’au n-ième. Il comprend deux boucles imbriquées, chacune effectuant n répétitions de son corps ; le corps de la boucle interne ne comporte qu’une multiplication. La complexité est
ici O(n 2 ).
6.1.3 Différentes nuances de complexité
Complexité au pire
Pour deux données de même taille, un algorithme n’effectue pas nécessairement le même
nombre d’opérations élémentaires. Par exemple, reprenons le test de primalité écrit au
chapitre 4.
premier = True
for i in range(2, int(sqrt(n))+1):
if n % i == 0:
premier = False
break
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
148
Informatique pour tous
Tableau 6.1 Ordres de grandeur des temps d’exécution
d’un problème de taille 10 6 sur un ordinateur à un milliard d’opérations par seconde (suite)
O(n k ) polynômiale
30 ans
si k = 3
Ici, n k est le terme de plus haut degré d’un polynôme en n ; il
n’est pas rare de voir des complexités en O(n 3 ) ou O(n 4 ).
O(2 n )
exponentielle plus de 10 300 000
milliards d’années
Un algorithme d’une telle complexité est impraticable sauf
pour de très petites données (n < 50). Comme pour la complexité logarithmique, la base de l’exponentielle ne change
fondamentalement rien à l’inefficacité de l’algorithme.
Exercice 6.2 Les algorithmes suivants calculent et affichent différentes listes de nombres. Quelle est la
complexité de chacun d’entre eux ?
def table1(n):
for i in range(11):
print(i * n)
def table2(n):
for i in range(n):
print(i * i)
def table3(n):
for i in range(n):
for j in range(n):
print(i * j, end=" ")
print()
• L’algorithme table1 affiche la table de multiplication de n jusqu’au rang 10. La boucle est toujours
exécutée 11 fois et ne comporte qu’une multiplication. Le temps d’exécution ne dépend donc pas de
l’entrée n : la complexité est O(1).
• L’algorithme table2 affiche la suite des carrés des nombres entiers jusqu’à (n − 1) 2 . La boucle est
exécutée n fois et ne comporte qu’une multiplication : la complexité est O(n).
• L’algorithme table3 construit une table de multiplication pour tous les entiers de 1 à n en donnant tous
leurs multiples jusqu’au n-ième. Il comprend deux boucles imbriquées, chacune effectuant n répétitions de son corps ; le corps de la boucle interne ne comporte qu’une multiplication. La complexité est
ici O(n 2 ).
6.1.3 Différentes nuances de complexité
Complexité au pire
Pour deux données de même taille, un algorithme n’effectue pas nécessairement le même
nombre d’opérations élémentaires. Par exemple, reprenons le test de primalité écrit au
chapitre 4.
premier = True
for i in range(2, int(sqrt(n))+1):
if n % i == 0:
premier = False
break