Chapitre 2 : Complexité des Algorithmes
Objectifs du chapitre
• Comprendre ce qu’est la complexité d’un algorithme.
• Différencier la complexité en temps et en espace.
• Utiliser les notations asymptotiques Big-O (O), Oméga (Ω), et Thêta (Θ).
• Savoir analyser le meilleur, le pire et le cas moyen d’un algorithme.
I. Qu’est-ce que la complexité ?
Définition :
La complexité mesure les ressources nécessaires (temps ou mémoire) pour qu’un algorithme
se termine, en fonction de la taille de l’entrée n.
Il ne s’agit pas du temps réel d’exécution mais du nombre d’opérations élémentaires
(comparaisons, affectations, boucles...).
II. Complexité en temps
Définition :
La complexité en temps est le nombre d’opérations que l’algorithme effectue pour résoudre
un problème.
Exemple :
Algorithme Affichage_0_n
Entrée : un entier n
Début
Pour i allant de 0 à n-1 faire
Afficher i
Fin Pour
Fin
Complexité en temps = O(n) (1 opération par tour, n tours).
III. Complexité en espace
Définition :
La complexité en espace est la quantité de mémoire utilisée par l’algorithme, en fonction de
n.
Exemple :
Algorithme Initialiser_Tableau
Entrée : un entier n
Début
Créer un tableau T de taille n
Pour i allant de 0 à n-1 faire
T[i] ← 0
Fin Pour
Fin
Complexité en espace = O(n) (la liste contient n éléments).
IV. Les notations asymptotiques
Ces notations permettent de décrire la complexité de manière générale, sans se soucier des
constantes.
1. Notation Big-O — O(f(n))
• Représente le pire des cas.
• Une borne supérieure du nombre d’opérations.
• Utilisée pour exprimer la croissance maximale.
Exemple : un algorithme de tri peut être O(n²) dans le pire des cas.
2. Notation Oméga (Ω) — Ω(f(n))
• Représente le meilleur des cas.
• Une borne inférieure.
• L’algorithme ne peut pas aller plus vite que ça.
Exemple : Ω(n) pour la recherche d’un élément dans une liste non triée.
3. Notation Thêta (Θ) — Θ(f(n))
• Lorsque le meilleur et le pire sont équivalents, on dit que l’algorithme est en
Θ(f(n)).
• C’est une borne serrée.
Exemple : un algorithme linéaire qui parcourt une liste exactement une fois ⇒ Θ(n).
V. Étude des cas : meilleur, moyen, pire
1. Meilleur cas (Best case)
• Conditions les plus favorables.
• Notation : Ω
Exemple : Recherche d’un élément en tête de liste ⇒ Ω(1)
2. Pire cas (Worst case)
• Conditions les plus défavorables.
• Notation : O
Exemple : Recherche d’un élément non présent dans une liste ⇒ O(n)
3. Cas moyen (Average case)
• Moyenne sur toutes les possibilités.
• Plus difficile à calculer.
• On peut l’exprimer aussi avec O, Ω ou Θ.
Exemple : Recherche d’un élément qui est quelque part au milieu ⇒ Θ(n)
VI. Tableau récapitulatif des complexités courantes
Complexité Nom Exemple
O(1) Constante Accès direct à une case
O(log n) Logarithmique Recherche dichotomique
O(n) Linéaire Parcours d’un tableau
O(n log n) Quasi-linéaire Tri fusion
O(n²) Quadratique Tri par sélection/insertion
O(2ⁿ) Exponentielle Problèmes NP-complets
O(n!) Factorielle Génération de permutations
Récapitulatif des types de complexité
1. Complexité constante – O(1)
Le temps d'exécution ne dépend pas de la taille des données.
Quand ?
• Accès direct à un élément d’un tableau (T[i])
• Affectation d'une variable
• Retour d'une valeur calculée sans boucle
Exemples :
• Lire la première case d’un tableau
• Calculer a + b
2. Complexité logarithmique – O(log n)
À chaque étape, on divise le problème en deux.
Quand ?
• Recherche dans des structures triées (diviser pour régner)
• Algorithmes de type dichotomie
Exemples :
• Recherche dichotomique dans un tableau trié
• Parcours d’un arbre binaire équilibré
3. Complexité linéaire – O(n)
Le temps croît proportionnellement à la taille des données.
Quand ?
• Parcours complet d’un tableau ou d’une liste
• Comptage ou somme d'éléments
Exemples :
• Trouver le maximum d’un tableau
• Afficher tous les éléments d’une liste
4. Complexité quasi-linéaire – O(n log n)
Croissance modérée, typique des algorithmes efficaces de tri.
Quand ?
• Algorithmes de tri optimisés (merge sort, quick sort en moyenne)
• Traitements sur des structures complexes équilibrées
Exemples :
• Tri fusion (merge sort)
• Tri rapide (quick sort)
• Construction d’un arbre binaire équilibré
5. Complexité quadratique – O(n²)
Deux boucles imbriquées sur la même structure.
Quand ?
• Comparaison de chaque élément avec les autres
• Algorithmes simples de tri ou de recherche naïve
Exemples :
• Tri par sélection ou insertion
• Recherche de doublons dans un tableau (comparaison brute)
• Produit matriciel naïf
6. Complexité exponentielle – O(2ⁿ)
Le temps double à chaque unité de plus. Inutilisable pour de grandes tailles.
Quand ?
• Problèmes combinatoires (parcours de toutes les possibilités)
• Algorithmes naïfs pour des problèmes NP-complets
Exemples :
• Problème du voyageur de commerce (brute force)
• Génération de tous les sous-ensembles d’un ensemble
7. Complexité factorielle – O(n!)
Cas extrême, explosion des calculs très rapide.
Quand ?
• Permutations complètes d’un ensemble
• Résolution exhaustive de problèmes avec ordre
Exemples :
• Génération de toutes les permutations d’un ensemble
• Problème des dames (approche brute)
À retenir
Complexité Efficacité Taille maximale gérable (~)
O(1) Très rapide Illimitée
O(log n) Très rapide Jusqu’à 1 milliard
O(n) Bonne Jusqu’à 10⁷
O(n log n) Efficace Jusqu’à 10⁶–10⁷
O(n²) Lente Jusqu’à 10³–10⁴
O(2ⁿ) Impraticable Jusqu’à 20–25
O(n!) Catastrophique Jusqu’à 10
VII. Exemple d’analyse complète
Algorithme :
Algorithme Somme_1_n
Entrée : un entier n
Sortie : un entier s (somme)
Début
s←0
Pour i allant de 1 à n faire
s←s+i
Fin Pour
Retourner s
Fin
• Temps :
o Boucle exécutée n fois ⇒ O(n)
• Espace :
o Variables s, i ⇒ O(1)
VIII. Exercices
Exercice 1 :
Analyser la complexité en temps et en espace de cet algorithme :
Algorithme Double_Affichage
Entrée : un tableau T de taille n
Début
Pour i allant de 0 à n-1 faire
Pour j allant de 0 à n-1 faire
Afficher T[i], T[j]
Fin Pour
Fin Pour
Fin
Exercice 2 :
Écrire un algorithme qui :
1. Crée une liste de n éléments.
2. Calcule la somme des éléments.
Algorithme Somme_Tableau
Entrée : un entier n
Sortie : un entier s
Début
Créer un tableau T de taille n
Pour i allant de 0 à n-1 faire
T[i] ← i
Fin Pour
s←0
Pour i allant de 0 à n-1 faire
s ← s + T[i]
Fin Pour
Retourner s
Fin
Demander :
• Complexité en temps ?
• Complexité en espace ?