Cours - Chapitre 6 - Complexité Algorithmique

Télécharger au format pdf ou txt
Télécharger au format pdf ou txt
Vous êtes sur la page 1sur 8

Partie II : Algorithmique et Programmation

SOMMAIRE

Chapitre 2 : La complexité algorithmique


I. Introduction.......................................................................................................................... 2
II. Notion de complexité ............................................................................................................ 3
1. Définition de la complexité d'un algorithme ....................................................................... 3
2. Types de complexité .......................................................................................................... 3
3. Comment mesurer la complexité d'un algorithme .............................................................. 3
4. Complexité et notation O .................................................................................................. 4
5. Différentes nuances de complexité .................................................................................... 6

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 :

1 - que remarquez-vous concernant cet exercice ?


2 - Le code le plus court ! Est-il meilleur ?
3 - Comment peut-on désigner le meilleur code parmi ces trois solutions ?

2
II. Notion de complexité

1. Définition de la complexité d'un algorithme

La complexité d'un problème mathématique P est une mesure de la quantité de ressources


nécessaires à la résolution du problème P.
Cette mesure est basée sur une estimation du nombre d'opérations de base effectuées par
l'algorithme en fonction de la taille des données en entrée de l'algorithme.
Généralement, pour le même problème P, on peut trouver plusieurs algorithmes (Alg1; Alg2 ;
... ; Algn).
L'objectif de la complexité est d'évaluer le coût d'exécution de chaque algorithme afin de
choisir le meilleur.

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.

Complexité temporelle (en temps) :


La complexité temporelle d'un algorithme est le nombre d'opérations élémentaires
(Affectations, comparaisons, opérations arithmétiques) effectuées par un algorithme.

Complexité spatiale (en espace) :


La complexité en mémoire donne le nombre d'emplacements mémoires occupés lors de
l'exécution d'un programme.

Remarque :
Dans ce cours, nous nous intéressons uniquement à la complexité temporelle.

3. Comment mesurer la complexité d'un algorithme

 Le coût des instructions élémentaires/composées

Opérations élémentaires :

On appelle opération de base, ou opération élémentaire, toute :


Affectation ;
Test de comparaison : == ; < ; <= ; >= ; ! =;
Opération de lecture (input) et écriture (print) ;
Opération arithmétique : + ; - ; *; / ;%;
Le coût d'une opération élémentaire est égal à 1.

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 :

On appelle opération composée, toute instruction contenant :

1. L'exécution d'une instruction conditionnelle : Si P est une instruction conditionnelle du type Si


b alors Q1 sinon Q2 finsi, le nombre d'opérations est :
Coût(P) <= Coût(test) + max(Coût(Q1), Coût(Q2))
2. L'exécution d'une boucle : le temps d'une boucle est égal à la multiplication de nombre de
répétition par la somme du coût de chaque instruction xi du corps de la boucle :
Coût(boucle for) =∑Coût(xi)
Coût(boucle while) = ∑(Coût(comparaison) + Coût(xi))

Exemple 2 : Que vaut le coût de l'algorithme B suivant :

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

Exemple 3 : Que vaut le coût de l'algorithme C suivant :

i=1
while i <= n :
somme=somme + i
i=i+1

Coût(C) = Coût(i <= n) + Coût(somme = somme + i) + Coût(i = i + 1)


= n+n+n
= 3n

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.

 Classes de complexité les plus usuelles

On voit souvent apparaître les complexités suivantes :

Complexité Nom courant Description

O(1) Constante Le temps d'exécution ne dépend pas des données


traitées, ce qui est assez rare !
Ex :
Ajouter un élément dans une liste
O(log(n)) Logarithmique Augmentation très faible du temps d'exécution quand le
paramètre croit.
Ex :
Couper un ensemble de données en deux parties égales,
puis couper ces moitiés en deux parties égales, etc.
O(n) Linéaire Augmentation linéaire du temps d'exécution quand
le paramètre croit (si le paramètre double, le temps
double).
Ex :
Parcourir un ensemble de données
O(n log(n)) Quasi-linéaire Augmentation un peu supérieure à O(n)
Ex :
Couper répétitivement un ensemble de données en deux
et combiner les solutions partielles pour calculer la
solution générale.
O(n2) Quadratique Quand le paramètre double, le temps d'exécution est
multiplié par 4.
Ex :
Algorithmes avec deux boucles imbriquées.
O(np ) Polynomiale Ici, np 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(n3)
ou O(n4).
Ex :
Parcourir un ensemble de données en utilisant p boucles
imbriquées
O(kn) Exponentielle Quand le paramètre double, le temps d'exécution est
élevé à la puissance k avec k > 1.
Ex :
Générer tous les sous-ensembles possibles d’un
ensemble de données.

5
 Comparaison de temps d'exécution

5. Différentes nuances de complexité

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.

Pour cela, on distingue 3 types de complexité :

 Complexité au pire des cas :

6
 Complexité dans le meilleur des cas :

Exemple 1 tri à bulle :

def tri_bulle (L) :


flag = True
while flag :
flag = False
for i in range(len(L)-1) :
if L[i]>L[i+1] :
L[i] , L[i+1] = L[i+1] , L[i]
flag = True

La complexité au pire des cas du tri à bulle :


Paramètre de complexité n = taille de la liste L
Pire des cas : tableau trié dans un ordre décroissant
En pire des cas la boucle while va se répéter n-1 fois
T(n) = 1 + (n-1)*(1+(n-2)*(1+3)) = O(n2)

La complexité au meilleur des cas du tri à bulle :


Paramètre de complexité n = taille de la liste L
Meilleur des cas : tableau trié en ordre croissant
En meilleur des cas la boucle while va se répéter une seule fois

7
T(n) = 1 + (1)*(1+(n-2)*(1+3)) = O(n)

Exemple 2 tri fusion :

def inserer(e, L):


R = L[:]
R.append(e)
i = len(R)-1
while i>0 and R[i]<R[i-1]:
R[i],R[i-1]=R[i-1],R[i]
i=i-1
return R

def fusionner(A, B):


R = A[:]
for e in B :
R = inserer(e,R)
return R

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:]))

La complexité au pire des cas du tri par fusion :


Après avoir facilement prouvé que la complexité de fusionner et inserer était O(n), on exprime la
complexité au pire cas de tri par (on néglige les instructions à faible coût):

2*T(n/2) + 2*n si n>=2


T(n) =
1 sinon

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

Par conséquent, T(2n) = log2(2n)·2n+1, et en majorant T(n) par T(2log2(n) )


on obtient T(n) = Θ(log2(n) · 2 log2(n)+1) = O(n · ln(n)). Cet algorithme est d’une complexité quasi-
linéaire.

Vous aimerez peut-être aussi