Cours - Chapitre 6 - Complexité Algorithmique
Cours - Chapitre 6 - Complexité Algorithmique
Cours - Chapitre 6 - Complexité Algorithmique
SOMMAIRE
1
La complexité algorithmique
I. Introduction
Exercice :
Ecrire en python une fonction qui recherche une valeur x dans une liste L, si elle appartient à L on
retourne son indice si non on retourne -1
Analysons plusieurs solutions
1. Première solution :
def recherche1(x, L) :
t = len(L)
i=0
while i < t :
if L[i]==x :
return i
i = i +1
return -1
2. Deuxième solution :
def recherche2(x, L) :
i=0
while i < len(L) :
if L[i]==x :
return i
i = i +1
return -1
3. Troisième solution :
def recherche3(x, L) :
for i in range(0, len(L)) :
if L[i]==x :
return i
return -1
Quelques questions :
2
II. Notion de complexité
Problème :
Comment évaluer le coût d'exécution d'un algorithme donné ?
2. Types de complexité
En fonction des ressources utilisées pour évaluer la complexité d'un algorithme, on sera
amené à distinguer deux types de complexité : complexité temporelle et complexité spatiale.
Remarque :
Dans ce cours, nous nous intéressons uniquement à la complexité temporelle.
Opérations élémentaires :
3
Exemple 1 : Que vaut le coût de l'algorithme A
somme = n + 1 #instr1
somme = somme + n #instr2
somme = somme/2 #instr3
Coût(A)=Coût(inst1)+Coût(instr2)+Coût(instr3) = 6
Opérations composées :
if i%2==0 :
n=i//2
else :
i=i+1
n=i//2
Coût(B) = Coût(i%2 == 0)+ max(Coût(n = i//2),Coût(i = i + 1; n = i//2))
= 2 + max(2,4)
=6
i=1
while i <= n :
somme=somme + i
i=i+1
4. Complexité et notation O
La notation O
Définition
Soit T(n) une fonction qui désigne le temps de calcul d'un algorithme A.
On dit que T(n) est en grand O de f(n) : T(n) = O(f (n)) si et seulement si : (n0; c) telle que T(n) <= c
* f (n) n >= n0
4
Exemples
Exemple 1 :
Si T(n) = 3n + 6 alors T(n) = O(n)
Démonstration :
En effet, pour n >= 2, on a 3n + 6 <= 9n ; la quantité 3n + 6 est donc bornée, à partir d'un certain rang,
par le produit de n et d'une constante.
Exemple 2 :
Si T(n) = n2 + 3n alors T(n) = O(n2)
Démonstration :
En effet, pour n >= 3, on a n2 + 3n <= 2n2 ; la quantité n2 + 3n est donc bornée, à partir d'un certain
rang, par le produit de n2 et d'une constante.
5
Comparaison de temps d'exécution
Il est fréquent que la complexité en temps soit améliorée au prix d'une augmentation de la complexité
en espace, et vice-versa.
La complexité dépend notamment :
De la puissance de la machine sur laquelle l'algorithme est exécuté,
Du langage et interpréteur (ou compilateur) utilisé pour coder l'algorithme, du style du
programmeur.
Pour des données de même taille, un algorithme n'effectue pas nécessairement le même
nombre d'opérations élémentaires.
6
Complexité dans le meilleur des cas :
7
T(n) = 1 + (1)*(1+(n-2)*(1+3)) = O(n)
def tri(L):
n = len(L)
if n==0 or n==1:
return L
m=(n-1)//2
return fusionner(tri(L[:m+1]),tri(L[m+1:]))
Pour les puissances de 2, on a T(2n) = 2 · T(2n−1 ) + 2 · 2 n et on va montrer par récurrence sur n que
T(2n) = n · 2n+1 :
T(2n ) = 2 · 2n + 2 · T(2n−1 )
= 2 · 2n + 2 · (n − 1) · 2n
= 2 · 2n + (n − 1) · 2n+1
= 2n+1 + (n − 1) · 2n+1
= n · 2n+1