Complexité d’un algorithme
Complexité d’un algorithme
Dwimi Omar
CRMEF FES-MEKNES. CPAM
21 novembre 2019
Complexité d’un algorithme
Ordre d’une application de N dans R∗+ .
Définition 1
Soit f et g deux applications de N dans R∗+ . On dit que f et g
ont le même ordre si f = O(g) et g = O(f ) ( à l’infini ). On note
f = Θ(g) (ou g = Θ(f ) )
"Avoir même ordre" est une relation d’équivalence sur l’espace
des fonctions de N dans R∗+ .
Complexité d’un algorithme
Introduction
Un algorithme efficace n’est pas seulement un algorithme qui
nous donne le résultat voulu avec une précision satisfaisante,
mais c’est aussi un algorithme qui s’exécute en un temps
acceptable.
Dans un algoruthme, chaque opération effectuée nécessite un
temps de traitement. Il y a plusieurs types d’opérations, celles
qu’on va considérer sont :
les tests.
les opérations arithmétique sur des données numériques
et souvent, ce sont les opérations arithmétiques qui ont plus
d’importance.
Complexité d’un algorithme
Compléxité d’un algorithme
Si n la taille de données prises par un algorithme, on note C (n)
le nombre des opérations effectuées par cet algorithme.
Définition 2
la complexité d’un algorithme est égale à l’ordre de sa fonction
de complexité C .
Complexité d’un algorithme
Complexités de référence
Coût constant : C (n) = Θ(1)
Coût logarithmique : C (n) = Θ(ln(n))
Coût linéaire : C (n) = Θ(n)
Coût quasi-linéaire : C (n) = Θ(n ln(n))
Coût quadratique : C (n) = Θ(n 2 )
Coût polynomial : C (n) = Θ(n p ) p ∈ N∗
Coût exponentiel : C (n) = Θ(x n ), x > 1
Complexité d’un algorithme
Pour avoir une idée ...
Pour un processeur effectuant 1 milliard d’opérations par
seconde, et pour une taille de taille n = 106 on a :
Θ(1) : 1 ns
Θ(ln(n)) : 15 ns
Θ(n) : 1 ms
Θ(n ln(n)) : 15 ms
Θ(n 2 ) : 15 min
Θ(n 3 ) : 30 ans
Θ(2n ) : 10300000 ans.
Complexité d’un algorithme
Exemple 1 : Puissance entière
Essayons d’écrire une fonction puissance(x,n) prenant en
paramètre un réel non nul x, un entier naturel n, et renvoie x n .
Complexité d’un algorithme
Exemple 1 : Puissance entière
Essayons d’écrire une fonction puissance(x,n) prenant en
paramètre un réel non nul x, un entier naturel n, et renvoie x n .
Méthode naïve
Complexité d’un algorithme
Exemple 1 : Puissance entière
Essayons d’écrire une fonction puissance(x,n) prenant en
paramètre un réel non nul x, un entier naturel n, et renvoie x n .
Méthode naïve
1 def puissance1(x,n):
2 if n==0:
3 return 1
4 p=x
5 for i in range(1,n):
6 p = p∗x
7 return p
Complexité d’un algorithme
Exemple 1 : Puissance entière
Essayons d’écrire une fonction puissance(x,n) prenant en
paramètre un réel non nul x, un entier naturel n, et renvoie x n .
Méthode naïve
1 def puissance1(x,n):
2 if n==0:
3 return 1
4 p=x
5 for i in range(1,n):
6 p = p∗x
7 return p
On peut aussi utiliser la récursivité
Complexité d’un algorithme
Exemple 1 : Puissance entière
Essayons d’écrire une fonction puissance(x,n) prenant en
paramètre un réel non nul x, un entier naturel n, et renvoie x n .
Méthode naïve
1 def puissance1(x,n):
2 if n==0:
3 return 1
4 p=x
5 for i in range(1,n):
6 p = p∗x
7 return p
On peut aussi utiliser la récursivité
1 def puissancerec(x,n):
2 if n==0:
3 return 1
4 else :
5 return x∗puissancerec(x,n−1)
Complexité d’un algorithme
Exemple 1 : Puissance entière
Essayons d’écrire une fonction puissance(x,n) prenant en
paramètre un réel non nul x, un entier naturel n, et renvoie x n .
Méthode naïve
1 def puissance1(x,n):
2 if n==0:
3 return 1
4 p=x
5 for i in range(1,n):
6 p = p∗x
7 return p
On peut aussi utiliser la récursivité
1 def puissancerec(x,n):
2 if n==0:
3 return 1
4 else :
5 return x∗puissancerec(x,n−1)
C’est un algorithme de complexité Θ(n).
Complexité d’un algorithme
Stratégie "diviser pour régner"
On calcule x n de la façon suivante :
1
n
si n = 0
n (x ) 2 si n et pair
x = 2
n−1
2
x(x 2 ) si n et impair
Complexité d’un algorithme
Stratégie "diviser pour régner"
On calcule x n de la façon suivante :
1
n
si n = 0
n (x ) 2 si n et pair
x = 2
n−1
2
x(x 2 ) si n et impair
1 def puissance2(x,n):
2 if n==0:
3 return 1
4 if n%2 == 0:
5 return puissance2(x,n//2)∗∗2
6 else :
7 return x∗puissance2(x,(n−1)//2)∗∗2
Exercice :
1 Montrer que le nombre d’appels dans la fonction
précédente est égal à blog2 (n)c + 1.
2 En déduire la complexité cet algorithme.
