Complexité algorithmique
Pourquoi mesurer la complexité ?
Section intitulée « Pourquoi mesurer la complexité ? »En pratique, on s’intéresse surtout à la complexité temporelle dans le pire des cas : il vaut mieux toujours envisager le scénario le plus défavorable.
Calcul de la complexité temporelle
Section intitulée « Calcul de la complexité temporelle »Règles de base
Section intitulée « Règles de base »Meilleur cas, pire cas, cas moyen
Section intitulée « Meilleur cas, pire cas, cas moyen »| Cas | Description | Exemple |
|---|---|---|
| Meilleur cas | Situation la plus favorable | Recherche d’un élément en première position |
| Pire cas | Situation la plus défavorable (la plus utilisée) | Élément absent d’un tableau → on parcourt tout |
| Cas moyen | Moyenne sur toutes les entrées possibles | Élément à une position aléatoire dans un tableau |
La notation Big O
Section intitulée « La notation Big O »En résumé : à partir d’une certaine taille d’entrée, l’algorithme ne dépassera jamais la courbe définie par f(n) multipliée par une constante.
Classes de complexité
Section intitulée « Classes de complexité »| Notation | Type | Exemple typique |
|---|---|---|
O(1) | Constante | Accès à un élément de tableau, calcul simple |
O(log n) | Logarithmique | Recherche dichotomique |
O(√n) | Racinaire | Recherche de diviseurs, Jump Search |
O(n) | Linéaire | Parcours simple d’un tableau |
O(n log n) | Quasi-linéaire | Tri fusion (Merge Sort), QuickSort (cas moyen) |
O(n²) | Quadratique | Boucles imbriquées, tri à bulles, tri par sélection |
O(n³) | Cubique | Multiplication de matrices naïve, algorithme de Floyd-Warshall |
O(aⁿ) | Exponentielle | Fibonacci naïf, sous-ensembles d’un ensemble |
O(n!) | Factorielle | Problème du voyageur de commerce (brute force), permutations |
Exemples concrets
Section intitulée « Exemples concrets »O(1) — Complexité constante
Section intitulée « O(1) — Complexité constante »Quel que soit le volume de données, l’algorithme effectue toujours le même nombre d’opérations.
FONCTION volumeSphère(rayon : réel) : réelCONSTANTE PI ← 3.14159VARIABLES volume : réelDÉBUT volume ← 4.0 / 3.0 * PI * rayon * rayon * rayon {1 opération} RETOURNER volumeFINQu’on lui donne un rayon de 1 ou de 1 000 000, le nombre d’opérations reste identique → O(1).
O(n) — Complexité linéaire
Section intitulée « O(n) — Complexité linéaire »Le nombre d’opérations croît proportionnellement à la taille de l’entrée.
FONCTION somme(T : tableau, n : entier) : entierVARIABLES somme, i : entiersDÉBUT somme ← 0 POUR i ← 0 À n - 1 FAIRE somme ← somme + T[i] {exécuté n fois} FIN_POUR RETOURNER sommeFINSi le tableau double de taille, le temps double → O(n).
O(log n) — Complexité logarithmique
Section intitulée « O(log n) — Complexité logarithmique »À chaque itération, on divise par 2 la portion à traiter. C’est le principe de la recherche dichotomique (dans un tableau trié).
FONCTION rechercheDichotomique(T : tableau, n : entier, cible : entier) : entierVARIABLES gauche, droite, milieu : entiersDÉBUT gauche ← 0 droite ← n - 1
TANT_QUE gauche <= droite FAIRE milieu ← (gauche + droite) / 2
SI T[milieu] == cible ALORS RETOURNER milieu SINON SI T[milieu] < cible ALORS gauche ← milieu + 1 SINON droite ← milieu - 1 FIN_SI FIN_TANT_QUE
RETOURNER -1 {non trouvé}FINSur un tableau de 1 000 000 éléments, on effectue au maximum 20 comparaisons → O(log n).
O(n²) — Complexité quadratique
Section intitulée « O(n²) — Complexité quadratique »Deux boucles imbriquées : pour chaque élément, on parcourt tous les autres.
POUR i ← 0 À n - 1 FAIRE POUR j ← 0 À n - 1 FAIRE {traitement} {exécuté n × n fois} FIN_POURFIN_POURSi n double, le temps est multiplié par 4 → O(n²). C’est la complexité des tris naïfs (bulles, sélection, insertion dans le pire cas).
Évolution comparée
Section intitulée « Évolution comparée »n = 10 n = 100 n = 1 000 n = 1 000 000
O(1) → 1 1 1 1O(log n) → 3 7 10 20O(n) → 10 100 1 000 1 000 000O(n log n)→ 33 664 10 000 20 000 000O(n²) → 100 10 000 1 000 000 10¹²O(2ⁿ) → 1 024 1.27 × 10³⁰ ... ...