COURS COMPLEXITE

INTODUCTION

La complexité est caractérisé la performance d’un algorithme sur les plans espace et temps

Les analyses que nous ferons le plus souvent seront les analyses sur le temps d’exécution

Parler de complexité revient à définir une relation d’équivalence appelée Relation de

complexité telle que 2 opérations sont en relation si et seulement si elles ont des temps
d’exécution appartenant à un même ordre de grandeur ; les ordres de grandeurs peuvent
être, par exemple,

 La nanoseconde
 La microseconde
 La milliseconde
 La seconde (pourquoi pas ?)

A priori, on définit une relation de complexité par défaut (RCD) comportant 4 classes
d’équivalence :

 M : Mémoire centrale (opérations qui s’exécutent en mémoire centrale)

 D : Disque dur
 L : Réseau local
 E : Réseau étendu

Ainsi notre RCD s’écrit RCD= (M, D, L, E)

Notons que chaque composante de notre MCD peut se décomposer en plusieurs sous
classes et ainsi de suite

Un principe pour améliorer l’efficacité des algorithmes est qu’étant donné qu’entres 2
ordres successifs de grandeurs de notre RCD (par exemple entre M et D) il y a au moins une
multiplication par 1000(Ainsi une addition en M est au moins 1000 fois plus rapide qu’une
opération en D), on se battra pour ramener autant que faire se peut nos données en M avant
de les traiter, et si c’est impossible, on essaye en D … Ce principe nous amène directement à
penser à l’algorithmique ensembliste ou les données sont traitées par blocs.

EVALUATION

Généralement on considère la complexité comme le nombre d’opérations effectuées pdt

l’exécution d’un algorithme

La complexité est caractérisée par un vecteur appelé vecteur de charge qui est quant a lui un
n-uplet de paramètres pouvant impacter sur le nombre d’opérations a effectuer. Il a deux
composantes :
-le vecteur de charge interne noté Vi
-le vecteur de charge externe noté Ve

Exemples :

Pour Xn , le vecteur de charge est V(n)

( nk ) le vecteur de charge est V (n,k)

√ X le vecteur de charge est V(x, tol)
Ordres de grandeur de complexité et comment produire un algorithme d’un ordre
de grandeur donné
C(n)=O(f(n)) ssi il existe c1 réel, tel que C(n)<=c1f(n)

C(n)=Θ (f(n)) ssi il existe c1,c2 réels, tel que c (n) est compris entre c 1 f (n) et c 2 f (n) à partir
d’un rang

O(1) nb opérations majoré par une constante, indépendante de n

O(lnn) : divise chaque par 2, et on fait des opérations de maxi O(1) avant et après la division, puis on
traite uniquement un coté de la division et de manière récursive.

A*b

Si b pair, a*b=(2a)*(b/2)

Sinon b=2k+1, k entier, donc ab=a(2k+1)=2ak+a=2a*(b-1)/2+a

Eq ab=a+(b-1)a

Produit(a,b)

Debut

Si b>a {//permute a,b

a=a+b;b=a-b; a=a-b;

Si b=0 retourner 0;

Si b pair retourner produit(2a,b/2);

Retourner produit(2a,b-1/2)+a ;// on peut aussi écrire produit(a,b-1)+a

fin

O(n)
O(nlnn) on divise par 2, et on fait sur chaque partie un traitement en O(taille de cette partie),

Et on traite récursivement chacune des parties

O(n2)

O(n2lnn)

O(nk), k>2

O(nklnn), k>2

O(en), O(n!)

Les types de complexité

3 types de complexités: meilleur des cas, pire des cas, cas moyen

Illustration: prenons le problème consistant à rechercher un nombre entier dans un tableau non trié
d’entiers, et à retourner sa position dans le tableau, et un nombre négatif si le nombre cherché n’est
pas dans le tableau.

Considérons l’algorithme qui part du début vers la fin du tableau, en comparant chaque fois
l’élément de la position courante au nombre recherché, et qui retourne la position si le nombre est
trouvé. A la fin, si le nombre n’a pas été trouvé, il retourne -1.

Quelle en est la complexité?

Si on est très «chanceux», dès le début on tombe sur l’élément à la première case du tableau. On a la
une complexité en O(1), qui ici correspond au meilleur des cas.

Le «malchanceux» ira jusqu’ à la fin du tableau, et fera une complexité en O(n) où n est la taille du
tableau, ce qui correspond au pire des cas.

Il se trouve que l’élément peut être à n’importe quelle position. S’il est à la position i, on fera k*i
opérations, où k est une constante. Vu qu’il peut être à n’importe quelle position, quelle sera sa
complexité moyenne? On parle alors de complexité dans le cas moyen. Elle se calcule comme étant

Cmoy=somme(c(i)*p(i))

Où C(i) est la complexité pour un cas donné noté cas i, et p(i) la probabilité que ce cas
survienne.
Règle générale de calcul de complexité
La complexité de l’algorithme se calcule en déterminant le nombre d’opérations (et non
d’instructions) nécessaires pour l’exécuter en fonction de paramètres donnés, considérés
comme caractéristiques des données d’entrée de l’algorithme.

En cas de boucle, on sommera toutes les opérations réalisées de la première à la dernière

entrée dans la boucle.

Si l’algorithme est récursif, on écrira une formule de récurrence entre les complexités de
diverses tailles du problème et on trouvera une solution à la récurrence.

Lorsque la complexité est aléatoire, on déterminera tout d’abord le pire des cas. S’il est
convenable, on peut s’arrêter. Sinon, on détermine le meilleur des cas s’il est mauvais aussi,
il vaut mieux chercher un autre algorithme. S’il est bon, on cherche alors la complexité dans
le cas moyen, en utilisant la formule d’espérance mathématique de la complexité.

La complexité d’un problème, c’est la plus petite complexité d’un algorithme capable de résoudre ce
problème.

Démarche détaillée de calcul de complexité

Calculer la complexité d'un algorithme, c'est déterminer comment le temps d'exécution (ou
l'espace mémoire utilisé) augmente en fonction de la taille de l'entrée. On mesure cette
complexité pour anticiper la performance de l'algorithme quand les données deviennent très
grandes. La complexité est souvent exprimée en termes de notation Big-O O(n)O(n)O(n), qui
donne un ordre de grandeur du temps ou de la mémoire nécessaire.

Voici les étapes pour calculer la complexité d'un algorithme :

1. Identifier les opérations de base

 Les opérations de base d'un algorithme sont celles qui prennent un temps constant, comme
l'accès à une variable, une opération arithmétique (addition, multiplication), ou une
affectation.
 En général, ce sont les instructions de base qui ne dépendent pas de la taille de l'entrée, par
exemple a = 5, x = x + 1, etc.
 Les opérations dont le nombre dépend de la taille de l'entrée sont celles qui vont influencer
la complexité globale.

2. Analyser les boucles

 Les boucles (for, while) sont souvent la source principale de complexité.

 Par exemple, une boucle for qui parcourt une liste de n éléments a une complexité en
temps O(n)O(n)O(n) car elle effectue une opération un nombre de fois proportionnel à n.
  Si une boucle est imbriquée dans une autre, par exemple un for à l'intérieur d'un autre for,
il faudra multiplier leurs complexités.

o Par exemple, une boucle for imbriquée dans une autre boucle for, chacune itérant
n fois, a une complexité de O(n2)O(n^2)O(n2).

3. Analyser les conditions (if-else)

 Les conditions elles-mêmes ne changent pas la complexité, mais les instructions dans chaque
branche doivent être analysées.
 Si une branche effectue une opération proportionnelle à la taille de l'entrée et l'autre
branche effectue une opération constante, on prend la branche la plus coûteuse pour le
calcul de la complexité.

4. Analyser les appels récursifs

 Si l'algorithme est récursif, la complexité peut être déterminée en établissant une relation de
récurrence.
 Par exemple, une fonction récursive qui appelle deux fois elle-même pour un problème de
taille n/2n/2n/2 aura une complexité de O(nlog⁡n)O(n \log n)O(nlogn) (comme dans le tri
fusion).
 Une fonction qui appelle récursivement une seule fois un sous-problème de taille n−1n-1n−1
a une complexité de O(n)O(n)O(n).

5. Combiner les résultats

 Si l'algorithme a plusieurs parties indépendantes, la complexité globale sera celle de la partie

la plus coûteuse.
 Par exemple, si une première étape prend O(n)O(n)O(n) et une seconde étape prend
O(n2)O(n^2)O(n2), la complexité totale est O(n2)O(n^2)O(n2) car c'est la partie la plus
importante lorsque nnn devient grand.

6. Utiliser la notation Big-O pour simplifier

 La notation Big-O permet de se concentrer sur le comportement asymptotique, c'est-à-dire le

terme qui croît le plus vite quand la taille de l'entrée augmente.
 On ignore les constantes et les termes de moindre importance.

o Par exemple, si la complexité est O(3n2+5n+10)O(3n^2 + 5n + 10)O(3n2+5n+10), on

simplifie en O(n2)O(n^2)O(n2).

Exemples Concrets

Exemple 1 : Boucle simple

python

Copier le code

for i in range(n):

print(i)

 Cette boucle exécute une opération simple nnn fois.

 Complexité : O(n)O(n)O(n).

Exemple 2 : Boucle imbriquée

python

Copier le code

for i in range(n):

for j in range(n):

print(i, j)

 La boucle extérieure s'exécute nnn fois, et pour chaque itération, la boucle intérieure
s'exécute aussi nnn fois.
 Donc, il y a n×n=n2n \times n = n^2n×n=n2 opérations.
 Complexité : O(n2)O(n^2)O(n2).

Exemple 3 : Boucle imbriquée avec une division

python

Copier le code

i = nwhile i > 1:

i=i/2

 À chaque itération, iii est divisé par 2. Cela se produit log⁡2(n)\log_2(n)log2(n) fois (car on
divise nnn par 2 jusqu'à atteindre 1).
 Complexité : O(log⁡n)O(\log n)O(logn).

Exemple 4 : Algorithme récursif (exemple avec la recherche

binaire)

python

Copier le code

def recherche_binaire(arr, target, low, high):

 if low > high:

return -1

mid = (low + high) // 2

if arr[mid] == target:

return mid

elif arr[mid] > target:

return recherche_binaire(arr, target, low, mid - 1)

else:

return recherche_binaire(arr, target, mid + 1, high)

 La recherche binaire divise la taille de l'entrée par 2 à chaque appel.

 Cela produit une complexité de O(log⁡n)O(\log n)O(logn).

Exemple 5 : Récursion double (exponentielle)

python

Copier le code

def fib(n):

if n <= 1:

return n

else:

return fib(n-1) + fib(n-2)

 Ici, chaque appel de fib(n) appelle deux autres appels (sauf pour les cas de base).
 Cela crée une complexité exponentielle O(2n)O(2^n)O(2n), car le nombre d'appels récursifs
double à chaque niveau.

Complexités courantes

Voici un tableau des complexités les plus courantes, de la plus rapide à la plus lente :

Notation Big-O Nom Exemple

O(1)O(1)O(1) Constant Accès direct à un élément

 Notation Big-O Nom Exemple

d'un tableau

O(log⁡n)O(\log n)O(logn) Logarithmique Recherche binaire

O(n)O(n)O(n) Linéaire Boucle simple

O(nlog⁡n)O(n \log Linéaire

Tri rapide, tri fusion
n)O(nlogn) logarithmique

O(n2)O(n^2)O(n2) Quadratique Boucle imbriquée

Algorithme récursif pour

O(2n)O(2^n)O(2n) Exponentielle
Fibonacci

O(n!)O(n!)O(n!) Factorielle Permutations d'une liste

Résumé

Pour déterminer la complexité :

1. Comptez les opérations de base.

2. Analysez les boucles et récursions.
3. Simplifiez en utilisant la notation Big-O.
4. Identifiez le terme dominant (celui qui croît le plus rapidement) et ignorez les constantes.

Avec un peu de pratique, cela deviendra plus intuitif, et vous pourrez rapidement estimer la
complexité des algorithmes !