La complexité d’un algorithme

1. Qu’est-ce que la complexité d’un algorithme ?

La complexité d’un algorithme est une mesure de la quantité de ressources (temps, mémoire) que l’algorithme utilise en fonction de la taille de l’entrée.

Complexité temporelle : combien de temps l’algorithme met pour s’exécuter.

Complexité spatiale : combien de mémoire il utilise.

Pourquoi s’intéresser à la complexité ?

Pour comparer différents algorithmes qui résolvent le même problème.

Pour prévoir les performances sur de grandes données.

Pour éviter que notre programme devienne trop lent ou gourmand en mémoire.

2. Notion de taille d’entrée

La complexité est souvent exprimée en fonction de la taille de l’entrée, notée n.

Par exemple, si on trie un tableau, n = le nombre d’éléments.

Si on recherche un mot dans un texte, n = le nombre de caractères.

3. Comment mesurer la complexité ?

On compte le nombre d’opérations élémentaires effectuées par l’algorithme en fonction de n (par exemple, comparaisons, additions).

Attention : On ne mesure pas le temps en secondes, car cela dépend de l’ordinateur, mais on cherche une estimation abstraite.

4. La notation Big O (Grand O)

La notation Big O (ou notation asymptotique) permet d’exprimer la complexité en se concentrant sur la croissance de l’algorithme quand n devient très grand, en ignorant les constantes et les termes de moindre importance.

Par exemple, si un algorithme fait :

3n² + 5n + 10 opérations,

on note sa complexité : O(n²) (car n² domine quand n grandit).

5. Les différentes complexités classiques

Voici les principales classes de complexité qu’on retrouve en algorithmique :

Complexité	Description	Exemples	Croissance (approximative)
O(1)	Temps constant	Accès à une case de tableau	Indépendant de n
O(log n)	Temps logarithmique	Recherche dichotomique	Croît très lentement
O(n)	Temps linéaire	Parcourir un tableau	Croît proportionnellement à n
O(n log n)	Temps quasi-linéaire	Tri fusion, tri rapide	Plus lent que O(n) mais efficace
O(n²)	Temps quadratique	Tri à bulle, tri insertion (pire cas)	Croît très vite avec n
$O(2^n)$	Temps exponentiel	Résolution de certains problèmes complexes (ex: certaines combinaisons)	Devient très vite énorme

Illustration graphique :

6. Exemples concrets

$O(1)$ : Lire un élément dans un tableau grâce à son indice.

$O(\log n)$ : Recherche dichotomique dans un tableau trié.

$O(n)$ : Parcourir une liste pour additionner tous les éléments.

$O(n \log n)$ : Tri par fusion.

$O(n²)$ : Tri par sélection, tri à bulle.

$O(2^n)$ : Résoudre le problème du voyageur de commerce naïvement (énumération de toutes les routes possibles).

7. Cas meilleur, pire et moyen

Meilleur cas : situation la plus favorable (ex : tableau déjà trié pour tri insertion).

Pire cas : situation la plus défavorable (ex : tableau inversé pour tri insertion).

Cas moyen : moyenne sur tous les cas possibles.

Souvent on s’intéresse au pire cas pour garantir la performance.

8. Pourquoi la complexité est importante au bac NSI ?

Pour choisir le bon algorithme selon la taille des données.

Pour comprendre pourquoi un algorithme peut être rapide ou lent.

Pour analyser et expliquer un programme lors d’une épreuve.