<< Page principale
1. Complexité
1.1. Définition
La complexité en informatique permet de définir la difficulté de résolution d'un problème.
Elle se définit en fonction du nombres d'opérations élémentaires à réaliser sur un traitement (complexité en temps).
Il existe également la complexité en espace qui définit la taille occupée par les données pour un problème donné.
Pour introduire une complexité, on utilise la notation $O(x)$ ou $x$ est une expression en fonction des données à traiter. Cette notation a été introduite par Paul Bachmann (1837-1920), mathématicien allemand, puis reprise par Edmund Landau (1877-1938), également mathématicien allemand. $O(x)$ signifie proportionnel à $x$ :
$∃α ∈ ℕ$, alors $O(αx)$ se notera $O(x)$.
Par exemple, calculer la moyenne de $n$ nombres est un traitement qui possède une compexité en $O(n)$ car il faut réaliser $n-1$ additions et une division, soit $n$ opérations arithmétiques.
Voici quelques ordres de grandeur :
| Expression | Exemple |
| $O(1)$ | lire une valeur dans un tableau en fonction de son indice |
| $O(n/2)$ | rechercher une valeur dans une liste de valeurs |
| $O(n × log(n))$ | trier un tableau de données avec une méthode efficace (quick sort) |
| $O(n^2)$ | trier un tableau de données avec une méthode pas très efficace (bubble sort) |
| $O(n^3)$ | faire le produit de deux matrices carrées de dimension $n$ |
| $O(n!)$ | maximum de parcimonie en bioinformatique |
| $O(e^n)$ | les échecs |
1.1.1. Complexité dans le meilleur et le pire des cas
Il est parfois difficile de donner une valeur exacte de la complexité. On procède alors en donnant :
- la complexité dans le meilleur des cas
- la complexité dans le pire des cas qui est l'expression que l'on retient pour la complexité d'un algorithme
- la complexité en moyenne qui est généralement la moyenne de la complexité dans le meilleur et dans le pire des cas
Exemple
Soit une liste ou un tableau de valeurs entières. Quelle est la complexité de la recherche d'une valeur dans cette liste ?
Le code Python est le suivant :
- import numpy as np
- def dans_liste(l,v):
- for valeur in liste:
- if valeur == v:
- return True
- return False
- valeur_a_trouver = input("quelle valeur trouver ? ")
- liste = np.random.randint(1,100,10)
- print(liste)
- print("recherche de la valeur ", valeur_a_trouver)
- if dans_liste(liste, valeur_a_trouver):
- print("oui la valeur est dans la liste")
- else:
- print("non valeur n'est pas dans la liste")
Voici également le code C de la recherche dans une liste :
- /**
- * recherche la valeur 'v' dans le tableau 't' de taille 'size'
- */
- bool dans_liste(int *t, int size, int v) {
- for (int i = 0; i < size; ++i) {
- if (t[ i ] == v) return true;
- }
- return false;
- }
- le meilleur des cas correspond au cas où la valeur est en première position dans la liste, la complexité est alors en $O(1)$
- le pire des cas correspond au cas où la valeur n'est pas dans la liste ou est en dernière position dans la liste, la complexité est alors en $O(n)$
La complexité en moyenne est donc la moyenne de ces deux complexités, soit $O({1 + n}/{2})$, simplifié en $O({n}/{2})$ mais comme $1/2$ est une constante entière, on doit normalement garder $O(n)$.
Exercice 1.1
Ecrire un programme de recherche dichotomique d'une valeur entière $v$ dans un tableau trié $t$. Donner la complexité de la recherche.
L'algorithme consiste à choisir deux bornes : $inf$ et $sup$ qui initialement sont affectées à $0$ et $taille(tableau)-1$.
A chaque étape on calcule $m = (inf + sup) /2$, puis :
- si $t[m] = v$ alors on retourne l'indice $m$
- si $v > t[m]$ alors $sup = m - 1$
- si $v < t[m]$ alors $inf = m + 1$
On continue tant que $inf ≤ sup$, sinon on retourne -1 pour indiquer que la valeur n'a pas été trouvée.
1.1.2. Complexité et données
La complexité ne prend pas en compte les données qui peuvent avoir une influence sur le temps d'exécution d'un algorithme.
L'exemple le plus simple pour comprendre ce concept est le tri d'un tableau de données. Prenons l'algorithme du tri à bulles :
- // Tri à bulles en Java
- public static void tri_a_bulles(int tab[]) {
- for (int i = tab.length-1; i > 0; --i) {
- for (int j = 0; j < i; ++j) {
- if (tab[j] > tab[j+1]) {
- // échange des données
- int tmp = tab[j];
- tab[j] = tab[j+1];
- tab[j+1] = tmp;
- }
- }
- }
- }
Voici l'évolution du tri sur un tableau trié en ordre inverse :
6 5 4 3 2 1
5 4 3 2 1 6
4 3 2 1 5 6
3 2 1 4 5 6
2 1 3 4 5 6
1 2 3 4 5 6
Ci dessous, on trouve les temps d'exécution d'un tri à bulles pour un tableau de 65_536 entiers en Java et en C++ avec des données :
- en ordre croissant (déjà triées)
- en ordre décroissant (triées en ordre inverse)
- aléatoires
| Langage / Données | croissant | décroissant | aléatoire |
| Java | 0,394 | 2,017 | 4,876 |
| C++ | 0,769 | 5,156 | 4,457 |
| Echanges | 0 | 2_147_450_880 | $≈$ 1_073_418_792 |
On observe qu'en fonction des données on aura un temps d'exécution rapide ou long. Cela est dû au nombre d'échanges de données :
- il est nul si les données sont triées
- important si les données sont triées en ordre inverse
- moyen si elles sont aléatoires
Cependant, on observe, en Java, que le temps d'exécution si les données sont en ordre décroissant est plus faible que celui des données aléatoires bien que le nombre d'échanges soit supérieur pour les données en ordre décroissant. Cela peut sembler contradictoire, mais en fait cela est dû à la prédiction de branchement.
1.1.3. Complexité et implantation
Nous venons de voir que bien que le nombre d'échanges soit plus important il peut engendrer un temps d'exécution plus court, ce qui est paradoxal mais normal du point de vue du microprocesseur.
Le cas du produit de matrices est emblématique de l'inadéquation qui peut résulter entre complexité et l'implantation d'un algorithme. On rappelle que le produit de deux matrices carrées de dimension $n$ est de la forme :
- void matrix_product(float *A, float *B, float *C, int n) {
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < n; ++j) {
- float c_i_j = 0;
- for (int k = 0; k < n; ++k) {
- c_i_j += A[i * n + k] * B[k * n + j];
- }
- C[i * n + j] = c_i_j;
- }
- }
- }
On doit pour chaque $c_i^j$ calculer : $$ c_{ i}^{j} = ∑↙{i=1}↖n a_i^k × b_k^j $$
On a donc un algorithme en $O(n^3)$. Il est possible de trouver des algorithmes de complexité plus faible comme celui de Strassen en $O(n^{2,807})$ mais qui n'est efficace que sur des matrices de grande taille.
Si on exécute l'algorithme du produit de matrices carrées de complexité $O(n^3)$ sur un Pentium E5300, on observe le comportement suivant :
Pour certaines dimensions de la matrice on observe des temps d'exécution anormalement élevés :
| n | temps n |
temps n-1 |
temps n+1 |
| 1024 | 25.39 | 7.26 | 7.24 |
| 1280 | 28.46 | 14.56 | 14.80 |
| 1536 | 84.37 | 25.59 | 25.77 |
| 1792 | 107.88 | 41.30 | 41.45 |
| 1920 | 72.07 | 51.17 | 51.32 |
| 2048 | 227.36 | 62.71 | 63.07 |
Ainsi, pour $n=2048$ on met 227 secondes pour effectuer le produit alors que pour $n = 2047$, on ne mettra que 62 secondes et 63 secondes pour $n = 2049$. L'explication est liée à l'ordre dans lequel on accède les données qui est très pénalisant pour certaines tailles de matrices et qui cause de nombreux défauts dans la mémoire cache.
Un défaut de cache signifie que la donnée n'est pas en mémoire cache et donc il faut la charger depuis la mémoire centrale.
1.2. Complexité et classes de problèmes
La théorie de la complexité cherche à classer les problèmes de décision selon la complexité des algorithmes capables de les résoudre
Il existe plusieurs classes de problèmes, dont les problèmes :
- P (Polynomiaux)
- NP (Polynomiaux non déterministes)
- NP-Complet
Voici plusieurs liens qui traitent du sujet :
- vidéo Nos algorithmes pourraient-ils être BEAUCOUP plus rapides ? (P=NP ?)
- vidéo P vs NP : une question fondamentale des mathématiques et de l'informatique - Passe-science #18
- vidéo Les problèmes NP-complets d'Olivier Bailleux, Université de Bourgogne
- cours Chapitre 8 : Classes de complexité P et NP de J. Bétréma, LaBRI
Pour résumer :
La classe P contient l'ensemble des problèmes polynomiaux, c'est à dire facile à résoudre et pour lesquels on peut exhiber un algorithme (en temps) polynomial, de la forme $n^k$.
la classe NP contient l'ensemble des problèmes polynomiaux non déterministes qui peuvent être résolus par un algorithme de complexité polynomiale pour une machine de Turing non déterministe : en d'autres termes on est capable d'examiner en parallèle un nombre important (éventuellement exponentiel de cas) mais un en temps polynomial.
Si un problème est NP-Complet, cela signifie qu'il n'existe pas d'autre choix (tant qu'on a pas démontré $P=NP$) que de passer par une recherche exhaustive afin d'en trouver une solution ou de montrer qu'il ne possède pas de solution.
Il est parfois possible, pour certaines instances, de trouver une propriété qui permette de résoudre simplement et efficacement le problème.
Rappels concernant les complexités :
| $n$ | $O(n)$ | $O(n × log(n))$ | $O(n × log_2(n))$ | $O(n^2)$ | $O(2^n)$ | $O(n!)$ |
| 10 | 10 | 10 | 33,21 | 100 | 1024 | 3,62 $10^6$ |
| 20 | 20 | 26,02 | 86,43 | 400 | 1,04 $10^{6}$ | 2,43 $10^{18}$ |
| 30 | 30 | 44,31 | 147,20 | 900 | 1,07 $10^{9}$ | 2,65 $10^{32}$ |
| 40 | 40 | 64,08 | 212,87 | 1600 | 1,09 $10^{12}$ | 8,15 $10^{47}$ |
| Notation | Définition |
| 𝑂(1) | constante |
| 𝑂(𝑙𝑜𝑔(𝑛)) | logarithmique |
| 𝑂(𝑛) | linéaire |
| 𝑂(𝑛×𝑙𝑜𝑔(𝑛)) | quasi-linéaire |
| 𝑂(𝑛2) | quadratique |
| 𝑂(𝑛3) | cubique |
| 𝑂(2𝑛) | exponentielle |
| 𝑂(𝑛!) | factorielle |
1.3. Exercices
Exercice 1.2
Quelle est la complexité de la fonction est_premier qui indique si un nombre est premier ou non ? Donner une implantation de cette fonction et en déduire la complexité.
Exercice 1.3
Soit le graphe suivant modélisé par la matrice donnée ci-après. Ecrire une fonction qui vérifie s'il existe un chemin entre deux sommets du graphe.
On représentera le graphe sous forme matricielle comme ceci :
| A | B | C | D | E | F | G | |
| A | 1 | 1 | |||||
| B | 1 | 1 | 1 | 1 | 1 | ||
| C | 1 | 1 | |||||
| D | 1 | 1 | 1 | ||||
| E | 1 | 1 | 1 | ||||
| F | 1 | 1 | |||||
| G | 1 |
Un 1 en ligne 'A' colonne 'B' signifie qu'il existe un arc entre les sommets 'A' et 'B'.
Pour déterminer s'il existe un chemin entre un sommet $X$ et un sommet $Y$, on peut procéder de manière non récursive en utilisant deux listes :
- la liste des sommets déjà visités l_visites, initialement composée de $X$
- la liste des sommets restant à visiter l_restant, initialement composée des sommets $Z$, tels qu'il existe un arc $(X,Z)$
L'algorithme de recherche est alors le suivant :
- // On part du sommet X et on recherche un chemin vers Y
- fonction recherche_chemin(G : graphe; X, Y : entiers) : booléen
- l_visités est liste entier = { X }
- l_restant est liste entier = [ Z, tels que il existe un arc (X,Z) dans G ]
- tant que non l_restant.est_vide() faire
- W = l_restant.premier()
- l_restant.supprimer( premier )
- si W = Y alors
- retourner Vrai
- fin si
- pour tout arc (W, Z) du graphe G faire
- si non (Z appartient à l_visités ou l_restant) alors
- l_restant.ajouter( W )
- fin si
- fin pour
- fin tant que
- retourner Faux
- fin fonction