Chapitre 03
Introduction au calcul de complexité
Introduction
La théorie de la complexité algorithmique vise à :
- classer les problèmes selon leur difficulté,
- classer les algorithmes selon leur efficacité,
- comparer les algorithmes résolvant un même problème.
Dans ce qui suit, nous allons étudier la complexité de :
- deux programmes différents pour vérifier la primalité d'un entier n
- Programme naïf : vérifier si n possède un diviseur dans l'intervalle [2, n-1]
- Programme rapide : vérifier si n possède un diviseur dans l'intervalle [2, √n]
- deux programmes différents pour calculer xn
- Méthode classique : Xn = X × X × ⋯ × X (n fois)
- Méthode d'exponentiation rapide :
- Si n est pair alors xn = (x2)n/2. Il suffit alors de calculer yn/2 avec y = x2.
- Si n est impair et n > 1, alors xn = x · (x2)(n-1)/2. Il suffit de calculer y(n-1)/2 avec y = x2 et de multiplier par x le résultat.
Mesure du temps d'exécution en Python
- Pour mesurer le temps d'exécution d'un programme en Python nous pouvons simuler un chronomètre :
- on le déclenche juste avant le début du programme,
- on l'arrête juste après la fin du programme,
- le temps écoulé entre les deux pressions est la durée qui nous intéresse.
- En Python, on peut simuler un chronomètre grâce au module time.
Exemple :
from time import*
debut = time() # on déclenche le chronomètre
# votre programme
fin = time() # on arrête le chronomètre
print('Temps écoulé:',fin-debut,'secondes')Calcul du temps d'exécution du programme naïf pour la vérification de la primalité d'un entier n
from time import *
from math import *
def premier(n):
for i in range(2,n):
if n%i==0:
return(False)
return(True)
a=time()
premier(2**31-1) # 2**31-1 est un nombre premier
print(time()-a," sec")Calcul du temps d'exécution du programme rapide pour la vérification de la primalité d'un entier n
from time import *
from math import *
def premierrapide(n):
for i in range(2,int(sqrt(n))+1):
if n%i==0:
return(False)
return(True)
a=time()
premierrapide(2**31-1)
print(time()-a," sec")Calcul du temps d'exécution de la méthode classique pour le calcul de xn
from time import *
def puissance(x,n):
r=1
for i in range(1,n+1):
r=r*x
return(r)
a=time()
puissance(3,2**20-1)
print(time()-a," sec")Calcul du temps d'exécution de la méthode d'exponentiation rapide pour le calcul de xn
from time import *
def puissancerapide(x,n):
r=1
while n>0:
if n%2!=0:
r=r*x
n=n//2
x=x*x
return(r)
a=time()
puissancerapide(3,2**20-1)
print(time()-a," sec")Dans l'étude de complexité d'un algorithme on ne mesure pas la durée en heures, minutes, secondes, ... :
- cela impliquerait d'implémenter les algorithmes qu'on veut comparer ;
- de plus, ces mesures ne seraient pas pertinentes car le même algorithme sera plus rapide sur une machine plus puissante.
- L'étude de complexité consiste donc à utiliser des unités de temps abstraites proportionnelles au nombre d'opérations effectuées.
- On pourra par la suite adapter ces quantités en fonction de la machine sur laquelle l'algorithme s'exécute.
Dans ce cours, on s'intéresse à l'étude de la complexité temporelle d'un algorithme ce qui consiste à calculer le nombre d'opérations élémentaires (affectations, comparaisons, opérations arithmétiques, …) effectuées par un algorithme. Ce nombre s'exprime en fonction de la taille n des données.
Dans l'étude de complexité d'un programme, on s'intéresse :
- La complexité au pire : temps d'exécution maximum, dans le cas le plus défavorable.
- La complexité au mieux : temps d'exécution minimum, dans le cas le plus favorable.
- La complexité moyenne : temps d'exécution dans un cas médian, ou moyenne des temps d'exécution.
Le plus souvent, on calcule la complexité au pire, car on veut borner le temps d'exécution d'un programme donné.
Calculer le coût d'un programme
Calculer le coût d'un programme revient à calculer le nombre d'opérations effectuées en fonction de la taille des données. 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 expression arithmétique (+, -, /, *, //, %, **) ayant en général un faible temps d'exécution 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 :
if b:
# bloc d'instructions p
else:
# bloc d'instructions qLe coût d'un test est égal au maximum des coûts des instructions p et q, plus le temps d'évaluation de l'expression booléenne b.
Le coût d'une boucle for :
for i in range(n):
# bloc d'instructions pLe coût d'une boucle for est égal au nombre de répétitions multiplié par le coût du bloc d'instructions p.
Quand le coût de p dépend de la valeur de i (compteur), le coût total de la boucle est la somme des coûts de p pour chaque valeur de i.
Le cas d'une boucle while :
while b:
# bloc d'instructions pLe cas d'une boucle 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 coût de l'exécution de la boucle par le nombre de répétitions effectuées.
Exemples de calcul de coût de plusieurs programmes dans le pire des cas
Calculer la factorielle d'un entier n
def factorielle(n):
fact=1 # 1 affectation
for i in range(2,n+1): # (n-1) itérations
fact=fact*i # 1 affectation + 1 multiplication
return(fact) # 1 renvoi
# tester la fonction
print(factorielle(4))Le coût du programme = Nombre total d'opérations élémentaires
1 affectation + (n-1) × (1 affectation + 1 multiplication) + 1 renvoi
f(n) = 1 + (n-1) × 2 + 1 = 2n
Vérifier la primalité d'un entier n
# Méthode naïve
def premier(n):
for i in range(2,n): # (n-2) itérations
if n%i==0: # 1 reste + 1 comparaison
return(False) # 1 renvoi
return(True) # 1 renvoif1(n) = (n-2) × 2 + 1 = 2n - 3
# Méthode rapide
def premierrapide(n):
for i in range(2,int(sqrt(n))+1): # (⌊√n⌋ - 1) itérations
if n%i==0: # 1 reste + 1 comparaison
return(False) # 1 renvoi
return(True) # 1 renvoif2(n) = (⌊√n⌋ - 1) × 2 + 1 = 2 × ⌊√n⌋ - 1
Pour n = 231 - 1 :
- f1(n) = 4 294 967 293 opérations élémentaires
- f2(n) = 92 679 opérations élémentaires
Calculer xn
Méthode classique :
# Méthode classique
def puissance(x,n):
r=1 # 1 affectation
for i in range(1,n+1): # n itérations
r=r*x # 1 affectation + 1 multiplication
return(r) # 1 renvoif1(n) = 1 + n × 2 + 1 = 2n + 2
Méthode d'exponentiation rapide :
# Méthode d'exponentiation rapide
def puissancerapide(x,n):
r=1 # 1 affectation
while n!=0: # (⌊log₂(n)⌋) itérations
if n%2!=0: # 1 reste + 1 comparaison
r=r*x # 1 affectation + 1 multiplication
n=n//2 # 1 affectation + 1 division
x=x*x # 1 affectation + 1 multiplication
return(r) # 1 renvoif2(n) = 1 + (⌊log₂(n)⌋ + 1) × (1+2+2+2) + (⌊log₂(n)⌋ + 1) × 2 + 1 = 9 × ⌊log₂(n)⌋ + 11
La représentation binaire de n nécessite (⌊log₂(n)⌋ + 1) bits.
Le coût maximal sur (⌊log₂(n)⌋ + 1) bits = 9 × ⌊log₂(n)⌋ + 11
Pour x = 3 et n = 220 - 1 :
- f1(n) = 2 097 152 opérations élémentaires
- f2(n) = 182 opérations élémentaires
Calculer le coût des programmes suivants
def somme1(n):
s=0 # 1 affectation
for i in range(1,n+1): # n itérations
s=s+i # 1 affectation + 1 addition
return(s) # 1 renvoif1(n) = 1 + n × 2 + 1 = 2n + 2
def somme2(n):
s=0 # 1 affectation
for i in range(1,n+1): # n itérations
for j in range(1,n+1): # n itérations
s=s+i*j # 1 affectation + 1 addition + 1 multiplication
return(s) # 1 renvoif2(n) = 1 + n × n × 3 + 1 = 3n² + 2
def somme3(n):
s=0 # 1 affectation
for i in range(1,n+1): # n itérations
for j in range(1,i+1): # i itérations
s=s+i*j # 1 affectation + 1 addition + 1 multiplication
return(s) # 1 renvoif3(n) = 1 + (n × (n+1)/2) × 3 + 1 = (3/2)n² + (3/2)n + 2
def puiss2(n):
i=1 # 1 affectation
while i<n: # ⌈log₂(n)⌉ itérations
i=i*2 # 1 affectation + 1 multiplication + 1 comparaison
return(i) # 1 comparaison + 1 renvoif4(n) = 1 + ⌈log₂(n)⌉ × 3 + 1 + 1 = 3 × ⌈log₂(n)⌉ + 3
Généralement, la complexité d'un algorithme est une mesure de sa performance asymptotique dans le pire des cas.
- Que signifie 'asymptotique' ?
- on s'intéresse à des données très grandes ;
- Que signifie 'dans le pire cas' ?
- on s'intéresse à la performance de l'algorithme dans les situations où le problème prend le plus de temps.
- Pourquoi ?
- pour être sûr que l'algorithme ne prendra jamais plus de temps que ce qu'on a estimé. Ce qui correspond à donner une majoration du nombre d'opérations effectuées par l'algorithme.
Notations asymptotiques
La notation O(.)
On dit que la complexité de l'algorithme est O(g(n)) où g est d'habitude une combinaison de polynômes, logarithmes ou exponentielles. Ce qui signifie que le nombre d'opérations effectuées, noté par f(n), est borné par C·g(n), où C est une constante, lorsque n tend vers l'infini.
Si f et g sont deux fonctions positives réelles : f(n) = O(g(n)) si et seulement si le rapport f/g est borné à l'infini (f est dominée par g) :
∃ C > 0, ∃ n0 > 0, ∀ n > n0, f(n) ≤ C·g(n)
La notation O, dite notation de Landau, vérifie les propriétés suivantes :
- si f = O(g) et g = O(h) alors f = O(h)
- si f = O(g) et a > 0, alors a · f = O(g)
- si f1 = O(g1) et f2 = O(g2) alors f1 + f2 = O(g1 + g2)
- si f1 = O(g1) et f2 = O(g2) alors f1 · f2 = O(g1 · g2)
La notation Ω(.)
Si f et g sont deux fonctions positives réelles : f(n) = Ω(g(n)) ⇒ g est une borne inférieure asymptotique pour f :
∃ C > 0, ∃ n0 > 0, ∀ n > n0, C·g(n) ≤ f(n)
La notation Θ(.)
Si f et g sont deux fonctions positives réelles : f(n) = Θ(g(n)) ⇒ f et g ont le même ordre de grandeur :
∃ C1, C2 > 0, ∃ n0 > 0, ∀ n > n0, C1·g(n) ≤ f(n) ≤ C2·g(n)
Classes de complexité
- O(1) : complexité constante, pas d'augmentation du temps d'exécution quand le paramètre croît.
- Exemple : affectation, comparaison, …
- O(log(n)) : complexité logarithmique, augmentation très faible du temps d'exécution quand le paramètre croît.
- Exemple : conversion du décimal au binaire
- O(n) : complexité linéaire, augmentation linéaire du temps d'exécution quand le paramètre croît (si le paramètre double, le temps double).
- Exemple : somme des n premiers entiers naturels
- O(n·log(n)) : complexité quasi-linéaire, augmentation un peu supérieure à O(n).
- Exemple : calculer la somme des chiffres des n premiers entiers naturels
- O(n²) : complexité quadratique, quand le paramètre double, le temps d'exécution est multiplié par 4.
- Exemple : algorithmes avec deux boucles imbriquées.
- O(ni) : complexité polynomiale, quand le paramètre double, le temps d'exécution est multiplié par 2i.
- Exemple : algorithme utilisant i boucles imbriquées.
- O(an) : complexité exponentielle, quand le paramètre double, le temps d'exécution est élevé à la puissance 2.
- O(n!) : complexité factorielle, asymptotiquement équivalente à nn.
L'évolution du temps de calcul en fonction de n pour quelques complexités usuelles
On suppose qu'on dispose d'un ordinateur capable de réaliser 109 opérations/seconde.
| n | log n | n log n | n² | 2n |
|---|---|---|---|---|
| 10 | 0.003 µs | 0.033 µs | 0.1 µs | 1 µs |
| 20 | 0.004 µs | 0.086 µs | 0.4 µs | 1 ms |
| 100 | 0.007 µs | 0.644 µs | 10 µs | 4 × 1013 ans |
| 1 000 000 | 0.020 µs | 19.93 ms | 16.7 min | — |
Règles de calcul de la complexité
- Les instructions de base (affectation, comparaison, opération arithmétique) prennent un temps constant, noté O(1).
- On additionne les complexités d'opérations en séquence :
Instruction p : O(f1(n))
Instruction q : O(f2(n))O(f1(n)) + O(f2(n)) = O(f1(n) + f2(n)) = O(max(f1(n), f2(n)))
- Les branchements conditionnels :
if <condition>: O(g(n))
# instructions (1) O(f1(n))
else:
# instructions (2) O(f2(n))= O(g(n) + f1(n) + f2(n)) = O(max(f1(n), f2(n), g(n)))
- La complexité d'une boucle for est égale au nombre d'itérations multiplié par la complexité de l'instruction p si ce dernier ne dépend pas de la valeur de i.
Python
for i in range (n): pO(n · f(n))
- La complexité d'une boucle while :
# en supposant qu'on a m itérations
while <condition>: O(g(n))
# instructions (1) O(f(n))= O(m · (g(n) + f(n))) = O(m · max(g(n), f(n)))
Calculer la complexité d'un programme
Pour calculer la complexité d'un programme :
- On calcule la complexité de chaque partie du programme,
- on combine ces complexités conformément aux règles qu'on vient de voir,
- on simplifie le résultat grâce aux règles de simplifications suivantes :
- On remplace les constantes multiplicatives par 1,
- on annule les constantes additives,
- on conserve le terme dominant.
Exemples
Exemple 1 : g(n) = 5n³ - 6n² + 4
- On remplace les constantes multiplicatives par 1 :
1·n³ - 1·n² + 4
- On annule les constantes additives :
1·n³ - 1·n²
- On conserve le terme dominant :
n³ - n²
- Solution :
g(n) = O(n³)
Exemple 2 : Fonction factorielle
def factorielle(n):
fact=1 # O(1)
i=2 # O(1)
while (i<=n): # n-1 itérations -> O(n)
fact = fact*i # O(1)
i=i+1 # O(1)
return(fact) # O(1)La complexité de la fonction factorielle :
O(1) + O(n) × O(1) + O(1) = O(n)
Exemple 3 : Boucles for avec différentes variations
for i in range(n):
..... # O(n)
for i in range(1,n+1,2):
..... # O(n)
for i in range(1,n//2):
..... # O(n)Exemple 4 : Boucles while avec division
i=1
while (i<n):
..... # O(log(n))
i=i*2
while (n!=0):
..... # O(log(n))
n=n//2
while (n!=0):
..... # O(log(n))
n=n//10Exercices avec corrigés
Énoncés
- Montrez que la complexité de la fonction suivante est quadratique en n, c'est-à-dire en O(n²) :
def calcul (n):
s=0
for k in range (n):
f = 1
for i in range (1, k+1):
f = f * i
s = s + 1.0/f
return(s)- Que fait cette fonction ?
- Donnez une version linéaire de cet algorithme, c'est-à-dire en O(n).
Calculer la complexité des programmes :
- premier et premier_rapide
- puissance et puissance_rapide
Dire si les affirmations suivantes sont vraies ou fausses :
- 2n + 3 = O(n)
- 2n + log(n) = O(n²)
- 2n7 + 5n4 + 3n² + 1 = O(n7)
- 5n³ + 3n·log(n) + 6n = O(n³)
- 3·log(n) + 2 = O(log(n))
- 2n + 100·log(n) = O(log(n))
- 2n+2 = O(2n)
Calculer la complexité des programmes suivants :
P1 :
p=0
for i in range(1,n*n+1):
j=i
while (j!=0):
p=p+1
j=j//2P2 :
for i in range(n):
for j in range(n):
x+=1P3 :
for i in range(n):
for j in range(i):
x+=1P4 :
for i in range(5, n-5):
for j in range(i-5, i+5):
x+=1P5 :
for i in range(n):
for j in range(i):
for k in range(j):
x+=1P6 :
i = n
while i>1:
x +=1
i /=2P7 :
i = n
while i>1:
for j in range(n):
x +=1
i /=2P8 :
i = n
while i>1:
for j in range(i):
x +=1
i /=2Corrigés
- Montrez que la complexité de la fonction suivante est quadratique en n, c'est-à-dire en O(n²) :
def calcul (n):
s=0 # 1 affectation
for k in range (n): # n itérations
f = 1 # 1 affectation
for i in range (1, k+1): # k itérations
f = f * i # 1 affectation + 1 multiplication
s = s + 1.0/f # 1 affectation + 1 addition + 1 division
return(s) # 1 renvoif(n) = 1 + n + 2 × (n × (n-1)/2) + 3n + 1 = n² + 3n + 2 = O(n²)
- Que fait cette fonction ? Calcul de exp(1)
- Donnez une version linéaire de cet algorithme, c'est-à-dire en O(n) :
def calculrapide (n):
s=0 # 1 affectation
f=1 # 1 affectation
for k in range (n): # n itérations
f = f * (k+1) # 1 affectation + 1 multiplication + 1 addition
s = s + 1.0/f # 1 affectation + 1 addition + 1 division
return(s) # 1 renvoif(n) = 2 + 6n + 1 = 6n + 3 = O(n)
Calculer la complexité, dans le pire des cas, des programmes : premier, premier_rapide, puissance et puissance_rapide.
Fonction premier :
def premier(n):
for i in range(2,n): # n-2 itérations -> O(n)
if n%i==0: # O(1)
return(False) # O(1)
return(True) # O(1)La complexité de la fonction premier :
O(n) × O(1) + O(1) = O(n)
Fonction premierrapide :
def premierrapide(n):
for i in range(2,int(sqrt(n))+1): # O(√n)
if n%i==0: # O(1)
return(False) # O(1)
return(True) # O(1)La complexité de la fonction premierrapide :
O(√n) × O(1) + O(1) = O(√n)
Fonction puissance :
def puissance(x,n):
r=1 # O(1)
for i in range(1,n+1): # n-1 itérations -> O(n)
r=r*x # O(1)
return(r) # O(1)La complexité de la fonction puissance :
O(1) + O(n) × O(1) + O(1) = O(n)
Fonction puissancerapide :
def puissancerapide(x,n):
r=1 # O(1)
while n>0: # O(log(n))
if n%2!=0: # O(1)
r=r*x # O(1)
n=n//2 # O(1)
x=x*x # O(1)
return(r) # O(1)La complexité de la fonction puissancerapide :
O(1) + O(log(n)) × O(1) + O(1) = O(log(n))
Dire si les affirmations suivantes sont vraies ou fausses :
- vrai : 2n + 3 = O(n)
- fausse : 2n + log(n) = O(n²)
- vrai : 2n7 + 5n4 + 3n² + 1 = O(n7)
- vrai : 5n³ + 3n·log(n) + 6n = O(n³)
- vrai : 3·log(n) + 2 = O(log(n))
- fausse : 2n + 100·log(n) = O(log(n))
- vrai : 2n+2 = O(2n)
- P1 : O(n²·log(n))
- P2 : O(n²)
- P3 : O(n²)
- P4 : O(n)
- P5 : O(n³)
- P6 : O(log(n))
- P7 : O(n·log(n))
- P8 : O(n)