Algorithmique et Complexité
Algorithmique et Complexité
Structures de données, algorithmes fondamentaux et analyse de complexité
Document pédagogique — Génie Informatique, 3ème année
Page 1
Algorithmique et Complexité
Sommaire
1. Introduction et notation asymptotique
2. Structures de données linéaires
3. Arbres et arbres binaires de recherche
4. Graphes : représentation et parcours
5. Algorithmes de tri
6. Algorithmes gloutons
7. Programmation dynamique
8. Algorithmes de recherche de plus court chemin
9. Classes de complexité P et NP
10. Conclusion et bonnes pratiques
Page 2
Algorithmique et Complexité
1. Introduction et notation asymptotique
Un algorithme est une suite finie et non ambiguë d'instructions permettant de résoudre un problème
donné. Au-delà de sa simple correction, l'évaluation d'un algorithme repose sur son efficacité, mesurée
en termes de temps d'exécution et d'espace mémoire consommé, en fonction de la taille des données
en entrée.
1.1 La notation Grand O
La notation asymptotique O(f(n)) décrit la borne supérieure de la croissance du temps d'exécution d'un
algorithme lorsque la taille n de l'entrée tend vers l'infini, en faisant abstraction des constantes
multiplicatives et des termes de moindre ordre. Elle permet de comparer des algorithmes
indépendamment du matériel utilisé.
Notation Nom Exem
O(1) Constante Accès
O(log n) Logarithmique Reche
O(n) Linéaire Parco
O(n log n) Quasi-linéaire Tri fus
O(n²) Quadratique Tri à b
O(2■) Exponentielle Résol
1.2 Complexités au meilleur, en moyenne et au pire des cas
L'analyse d'un algorithme distingue généralement trois scénarios : la complexité dans le meilleur des
cas (borne inférieure optimiste), la complexité moyenne (attendue statistiquement sur des entrées
aléatoires) et la complexité dans le pire des cas (borne supérieure garantie). C'est généralement cette
dernière qui est retenue en pratique, car elle garantit une performance minimale quelles que soient les
données fournies.
1.3 Complexité spatiale
Outre le temps d'exécution, la complexité spatiale mesure la quantité de mémoire supplémentaire
requise par un algorithme, en fonction de la taille de l'entrée. Un algorithme dit « en place » (in-place)
n'utilise qu'un espace mémoire supplémentaire constant, indépendamment de la taille des données
traitées.
Page 3
Algorithmique et Complexité
2. Structures de données linéaires
Les structures de données linéaires organisent les éléments selon un ordre séquentiel, chaque élément
possédant, à l'exception des extrémités, exactement un prédécesseur et un successeur.
2.1 Tableaux et listes chaînées
Un tableau (array) stocke des éléments dans des cases contiguës en mémoire, ce qui permet un accès
direct en temps constant O(1) via un indice, mais rend coûteuse toute insertion ou suppression en
milieu de structure, en O(n). Une liste chaînée, à l'inverse, relie chaque élément (nœud) au suivant par
un pointeur, ce qui autorise des insertions et suppressions en O(1) une fois la position localisée, au prix
d'un accès séquentiel obligatoire, en O(n), pour atteindre un élément donné.
2.2 Piles (stacks)
Une pile est une structure de données respectant le principe LIFO (Last In, First Out) : le dernier
élément inséré est le premier à être retiré. Les opérations fondamentales sont empiler (push) et dépiler
(pop), toutes deux réalisables en O(1). Les piles interviennent notamment dans la gestion des appels
de fonctions récursives, l'évaluation d'expressions arithmétiques ou l'algorithme de parenthésage.
2.3 Files (queues)
Une file respecte le principe FIFO (First In, First Out) : le premier élément inséré est le premier retiré.
Les opérations principales sont enfiler (enqueue) et défiler (dequeue). Les files sont utilisées dans la
gestion des tâches en attente, l'ordonnancement de processus ou encore le parcours en largeur des
graphes.
class Pile:
def __init__(self):
[Link] = []
def empiler(self, valeur):
[Link](valeur)
def depiler(self):
if not [Link]:
raise IndexError("Pile vide")
return [Link]()
def sommet(self):
return [Link][-1]
2.4 Tables de hachage
Une table de hachage associe à chaque clé, via une fonction de hachage, un index dans un tableau où
est stockée la valeur correspondante. En moyenne, les opérations d'insertion, de recherche et de
suppression s'effectuent en temps constant O(1), ce qui en fait l'une des structures les plus
performantes pour l'accès associatif. La gestion des collisions, lorsque deux clés distinctes produisent
le même indice, se fait généralement par chaînage ou par adressage ouvert.
Page 4
Algorithmique et Complexité
3. Arbres et arbres binaires de recherche
Un arbre est une structure de données hiérarchique composée de nœuds reliés par des arêtes, sans
cycle, avec un nœud racine unique et, pour chaque nœud, un unique chemin le reliant à la racine.
3.1 Vocabulaire des arbres
• Racine : nœud unique n'ayant aucun parent.
• Feuille : nœud ne possédant aucun enfant.
• Hauteur : longueur du plus long chemin entre la racine et une feuille.
• Arbre binaire : arbre dans lequel chaque nœud possède au plus deux enfants (gauche et droit).
3.2 Arbre binaire de recherche (ABR)
Un arbre binaire de recherche impose, pour chaque nœud, que toutes les valeurs du sous-arbre
gauche lui soient strictement inférieures, et que toutes les valeurs du sous-arbre droit lui soient
strictement supérieures. Cette propriété permet une recherche par dichotomie descendante le long de
l'arbre, offrant une complexité en O(log n) pour un arbre équilibré, mais dégénérant en O(n) dans le
pire des cas d'un arbre déséquilibré (par exemple lors d'une insertion de données déjà triées).
def inserer(noeud, valeur):
if noeud is None:
return Noeud(valeur)
if valeur < [Link]:
[Link] = inserer([Link], valeur)
else:
[Link] = inserer([Link], valeur)
return noeud
3.3 Arbres équilibrés
Afin de garantir une hauteur logarithmique quel que soit l'ordre d'insertion, des structures
auto-équilibrées ont été développées : l'arbre AVL, qui maintient une différence de hauteur bornée
entre sous-arbres gauche et droit via des rotations, ou l'arbre rouge-noir, qui applique un ensemble de
règles de coloration garantissant un équilibre approximatif tout en limitant le nombre de rotations
nécessaires. Ces structures sont largement utilisées dans l'implémentation des conteneurs ordonnés
des bibliothèques standard des langages de programmation.
3.4 Parcours d'arbres
Trois parcours en profondeur sont classiquement définis sur les arbres binaires : le parcours préfixe
(racine, gauche, droite), le parcours infixe (gauche, racine, droite), qui produit les valeurs triées dans un
ABR, et le parcours postfixe (gauche, droite, racine). Le parcours en largeur (BFS), quant à lui, explore
l'arbre niveau par niveau à l'aide d'une file.
Page 5
Algorithmique et Complexité
4. Graphes : représentation et parcours
Un graphe est une structure composée d'un ensemble de sommets (ou nœuds) reliés par des arêtes.
On distingue les graphes orientés, où chaque arête possède un sens, des graphes non orientés. Les
arêtes peuvent également être pondérées, associant un coût numérique à chaque liaison.
4.1 Représentations en mémoire
• Matrice d'adjacence : tableau bidimensionnel de taille n×n indiquant la présence (et le poids
éventuel) d'une arête entre chaque paire de sommets ; accès en O(1) mais espace en O(n²),
adapté aux graphes denses.
• Liste d'adjacence : chaque sommet est associé à la liste de ses voisins ; espace en O(n + m) où m
est le nombre d'arêtes, adapté aux graphes creux, majoritaires en pratique.
4.2 Parcours en largeur (BFS)
Le parcours en largeur (Breadth-First Search) explore un graphe niveau par niveau à partir d'un
sommet source, à l'aide d'une file. Il garantit de trouver le plus court chemin en nombre d'arêtes dans
un graphe non pondéré, avec une complexité en O(n + m).
4.3 Parcours en profondeur (DFS)
Le parcours en profondeur (Depth-First Search) explore un graphe en s'enfonçant le plus loin possible
le long de chaque branche avant de revenir en arrière (backtracking), généralement implémenté
récursivement ou à l'aide d'une pile explicite. Il est utilisé notamment pour détecter des cycles,
effectuer un tri topologique ou identifier les composantes connexes d'un graphe.
def dfs(graphe, sommet, visites=None):
if visites is None:
visites = set()
[Link](sommet)
for voisin in graphe[sommet]:
if voisin not in visites:
dfs(graphe, voisin, visites)
return visites
Page 6
Algorithmique et Complexité
5. Algorithmes de tri
Le tri d'une collection de données constitue l'un des problèmes les plus étudiés en algorithmique, tant il
conditionne l'efficacité de nombreux traitements ultérieurs comme la recherche dichotomique.
5.1 Tri à bulles
Le tri à bulles compare successivement chaque paire d'éléments adjacents et les échange s'ils sont
mal ordonnés, répétant ce processus jusqu'à ce qu'aucun échange ne soit plus nécessaire. Simple à
comprendre mais peu performant, il présente une complexité de O(n²) dans le pire des cas.
5.2 Tri par insertion
Le tri par insertion construit progressivement une sous-liste triée en y insérant chaque nouvel élément
à sa position correcte. Il est particulièrement efficace sur de petites listes ou des listes déjà quasiment
triées, avec une complexité de O(n²) dans le pire des cas mais O(n) dans le meilleur des cas.
5.3 Tri fusion (merge sort)
Le tri fusion applique le paradigme diviser pour régner : il divise récursivement la liste en deux moitiés
jusqu'à obtenir des sous-listes d'un seul élément, puis fusionne ces sous-listes triées deux à deux. Sa
complexité garantie de O(n log n), quel que soit le cas, en fait un algorithme de tri stable et fiable, au
prix d'un espace mémoire supplémentaire en O(n).
5.4 Tri rapide (quicksort)
Le tri rapide sélectionne un élément pivot, puis partitionne la liste de sorte que tous les éléments
inférieurs au pivot soient placés avant lui et tous les éléments supérieurs après, avant d'appliquer
récursivement le même procédé aux deux sous-listes obtenues. Sa complexité moyenne est en O(n log
n), mais peut dégénérer en O(n²) dans le pire des cas, notamment lorsque le pivot est
systématiquement mal choisi sur des données déjà triées.
def quicksort(liste):
if len(liste) <= 1:
return liste
pivot = liste[len(liste) // 2]
gauche = [x for x in liste if x < pivot]
milieu = [x for x in liste if x == pivot]
droite = [x for x in liste if x > pivot]
return quicksort(gauche) + milieu + quicksort(droite)
5.5 Comparatif des algorithmes de tri
Algorithme Meilleur cas Pire cas
Tri à bulles O(n) O(n²)
Tri par insertion O(n) O(n²)
Tri fusion O(n log n) O(n log n)
Tri rapide O(n log n) O(n²)
Tri par tas (heapsort) O(n log n) O(n log n)
Page 7
Algorithmique et Complexité
Page 8
Algorithmique et Complexité
6. Algorithmes gloutons
Un algorithme glouton (greedy) construit une solution étape par étape, en effectuant à chaque étape le
choix localement optimal, sans jamais revenir sur ses décisions antérieures, dans l'espoir d'aboutir à
une solution globalement optimale.
6.1 Conditions d'application
Une approche gloutonne ne garantit une solution optimale que si le problème présente deux propriétés
: la sous-structure optimale, selon laquelle une solution optimale du problème global contient des
solutions optimales de ses sous-problèmes, et la propriété de choix glouton, selon laquelle un choix
localement optimal effectué en premier n'empêche jamais d'atteindre une solution globalement
optimale.
6.2 Exemples classiques
• Rendu de monnaie : en choisissant systématiquement la plus grande pièce ou le plus grand billet
disponible ne dépassant pas le montant restant (optimal pour certains systèmes monétaires
seulement).
• Algorithme de Kruskal / Prim : construction d'un arbre couvrant de poids minimal en sélectionnant
à chaque étape l'arête de moindre coût ne créant pas de cycle.
• Algorithme de Huffman : construction d'un code de compression optimal en fusionnant
itérativement les deux symboles de fréquence la plus faible.
• Problème du sac à dos fractionnaire : sélection des objets par rapport valeur/poids décroissant,
contrairement à sa variante 0/1 qui nécessite la programmation dynamique.
Page 9
Algorithmique et Complexité
7. Programmation dynamique
La programmation dynamique est une technique de résolution de problèmes d'optimisation qui
décompose un problème en sous-problèmes chevauchants, résout chacun d'eux une seule fois, et
mémorise les résultats intermédiaires afin d'éviter tout recalcul redondant. Elle s'applique aux
problèmes possédant une sous-structure optimale et des sous-problèmes qui se recoupent.
7.1 Approche descendante (mémoïsation)
L'approche descendante conserve la structure récursive naturelle du problème, mais stocke chaque
résultat calculé dans une table (souvent un dictionnaire), consultée avant tout nouveau calcul afin
d'éviter de résoudre à nouveau un sous-problème déjà traité.
7.2 Approche ascendante (tabulation)
L'approche ascendante construit itérativement la solution en partant des plus petits sous-problèmes
jusqu'au problème initial, en remplissant progressivement une table de résultats, ce qui élimine le
surcoût des appels récursifs.
def fibonacci_dynamique(n):
if n <= 1:
return n
table = [0] * (n + 1)
table[1] = 1
for i in range(2, n + 1):
table[i] = table[i - 1] + table[i - 2]
return table[n]
# Complexite : O(n) au lieu de O(2^n) pour la version recursive naive
7.3 Exemples classiques
• Suite de Fibonacci : passage d'une complexité exponentielle à une complexité linéaire grâce à la
mémoïsation.
• Problème du sac à dos 0/1 : détermination de la combinaison d'objets maximisant la valeur sans
dépasser une capacité donnée.
• Plus longue sous-séquence commune (LCS) : comparaison de deux séquences, utilisée
notamment dans les outils de comparaison de fichiers.
• Distance d'édition (Levenshtein) : nombre minimal d'opérations pour transformer une chaîne en
une autre, utilisé en correction orthographique.
Page 10
Algorithmique et Complexité
8. Algorithmes de recherche de plus court chemin
8.1 Algorithme de Dijkstra
L'algorithme de Dijkstra détermine le plus court chemin entre un sommet source et tous les autres
sommets d'un graphe pondéré à poids positifs. Il maintient une estimation de distance pour chaque
sommet, sélectionne à chaque étape le sommet non traité de plus faible distance estimée, et met à jour
les distances de ses voisins (opération de relaxation). Sa complexité, en s'appuyant sur un tas binaire
(min-heap), est de O((n + m) log n).
8.2 Algorithme de Bellman-Ford
Contrairement à Dijkstra, l'algorithme de Bellman-Ford tolère la présence d'arêtes de poids négatif et
permet de détecter l'existence d'un cycle absorbant (de poids total négatif). Il relâche l'ensemble des
arêtes du graphe n-1 fois, où n est le nombre de sommets, ce qui lui confère une complexité en O(n ×
m), plus élevée que celle de Dijkstra.
8.3 Algorithme A*
L'algorithme A* (A star) enrichit le principe de Dijkstra en intégrant une heuristique admissible qui
estime la distance restante jusqu'à la destination, orientant ainsi la recherche de manière plus efficace
vers l'objectif. Il est largement employé dans les systèmes de navigation GPS et l'intelligence artificielle
des jeux vidéo pour le déplacement de personnages.
Page 11
Algorithmique et Complexité
9. Classes de complexité P et NP
La théorie de la complexité classifie les problèmes algorithmiques selon les ressources (temps,
mémoire) nécessaires à leur résolution, indépendamment de tout algorithme particulier.
9.1 La classe P
La classe P regroupe l'ensemble des problèmes de décision solubles par un algorithme déterministe en
temps polynomial par rapport à la taille de l'entrée. Ces problèmes sont considérés comme «
efficacement solubles » en pratique.
9.2 La classe NP
La classe NP regroupe les problèmes de décision dont une solution proposée peut être vérifiée en
temps polynomial, sans que l'on sache nécessairement la trouver efficacement. Tout problème de la
classe P appartient également à NP, mais la question de savoir si P est strictement inclus dans NP, ou
si les deux classes sont en réalité identiques (P = NP), demeure l'un des plus grands problèmes
ouverts des mathématiques et de l'informatique théorique.
9.3 Problèmes NP-complets
Un problème est dit NP-complet s'il appartient à NP et si tout autre problème de NP peut s'y ramener
en temps polynomial. Résoudre efficacement un seul problème NP-complet permettrait donc de
résoudre efficacement tous les problèmes de NP. Le problème de satisfaisabilité booléenne (SAT), le
problème du voyageur de commerce ou la coloration de graphes en sont des exemples classiques,
rencontrés fréquemment dans les applications d'optimisation industrielle.
Page 12
Algorithmique et Complexité
10. Conclusion et bonnes pratiques
La maîtrise de l'algorithmique et de l'analyse de complexité constitue un socle fondamental pour tout
ingénieur informatique, car elle conditionne directement la capacité à concevoir des solutions
performantes et adaptées à l'échelle des données traitées, un enjeu d'autant plus critique à l'ère des
grands volumes de données.
Au-delà de la connaissance théorique des structures et algorithmes présentés dans ce document, leur
mise en pratique régulière, notamment via des plateformes d'entraînement telles que LeetCode,
HackerRank ou Codeforces, demeure le meilleur moyen de développer une intuition solide pour choisir
la structure de données et l'algorithme les plus appropriés face à un problème donné.
Enfin, il convient de rappeler qu'un algorithme théoriquement optimal n'est pas toujours le meilleur
choix pratique : la simplicité, la lisibilité du code et les constantes cachées derrière la notation
asymptotique doivent également entrer en ligne de compte lors de la conception de systèmes réels.
Page 13