Un algorithme est une suite finie et non ambiguë d’étapes qui transforme des données initiales en un résultat vérifiable. Les dix méthodes de cet article sont très connues parce qu’elles expriment des idées réutilisables : réduire l’espace de recherche, diviser un problème, parcourir un réseau, conserver des résultats partiels ou exploiter les fréquences.
Il n’existe pas d’algorithme universellement meilleur. Une méthode est efficace lorsqu’elle est correcte pour les données disponibles, respecte les contraintes de temps et de mémoire et garantit le résultat demandé. Le pseudo-code sert à comprendre l’idée ; dans une application réelle, il convient d’utiliser des bibliothèques reconnues et bien testées.
Comment lire les complexités
La notation O(...) décrit la croissance du coût lorsque l’entrée augmente ; ce n’est pas une durée en secondes. Dans cet article, n désigne le nombre d’éléments, V les sommets d’un graphe, E ses arêtes, m la longueur du motif, W la capacité du sac, k le nombre de symboles distincts et L la longueur du message.
| Ordre | Interprétation pratique |
|---|---|
O(1) | Le coût n’augmente pas avec la taille de l’entrée. |
O(log n) | Chaque étape réduit fortement le problème, souvent de moitié. |
O(n) | Le travail augmente proportionnellement au nombre d’éléments. |
O(n log n) | Coût typique des tris généraux efficaces. |
O(n²) | Le coût peut croître rapidement pour de grandes entrées. |
1. Algorithme d’Euclide
Objectif. Calculer le plus grand commun diviseur de deux entiers sans énumérer tous leurs diviseurs.
Idée fondamentale. Si a = qb + r, les diviseurs communs de a et b sont les mêmes que ceux de b et du reste r. On remplace donc la paire par (b, a mod b) jusqu’à ce que le reste soit nul.
Pseudo-code
PGCD(a, b)
a ← valeur_absolue(a)
b ← valeur_absolue(b)
TANT_QUE b ≠ 0
(a, b) ← (b, a mod b)
RENVOYER aExemple détaillé. Pour PGCD(252, 105) : 252 mod 105 = 42, 105 mod 42 = 21 et 42 mod 21 = 0. Le dernier reste non nul est 21.
Complexité. Temps O(log min(a,b)) et mémoire O(1) pour la version itérative.
Quand l’utiliser. Pour simplifier des fractions, tester si deux nombres sont premiers entre eux, calculer des périodes et préparer des opérations d’arithmétique modulaire. La version étendue trouve aussi les coefficients de Bézout et les inverses modulaires.
Limite importante. Le cas PGCD(0,0) doit être défini séparément, car il est indéterminé ; cet algorithme ne constitue pas à lui seul un système cryptographique.
2. Recherche dichotomique
Objectif. Trouver une valeur dans une suite triée sans examiner chaque élément.
Idée fondamentale. On compare la valeur recherchée à l’élément central. Cette comparaison élimine la moitié qui ne peut pas contenir la réponse, puis on recommence uniquement dans l’intervalle restant.
Pseudo-code
RECHERCHE_DICHOTOMIQUE(A, x)
gauche ← 0
droite ← longueur(A) − 1
TANT_QUE gauche ≤ droite
milieu ← gauche + partie_entiere((droite − gauche) / 2)
SI A[milieu] = x RENVOYER milieu
SI A[milieu] < x
gauche ← milieu + 1
SINON
droite ← milieu − 1
RENVOYER non_trouveExemple détaillé. On cherche 23 dans [3, 8, 12, 17, 23, 31]. La première valeur centrale est 12 : on élimine la partie gauche ; la nouvelle valeur centrale est 23 et la recherche s’arrête.
Complexité. Temps O(log n) et mémoire O(1) dans la forme itérative.
Quand l’utiliser. Sur des tableaux triés avec accès rapide par indice ; également pour trouver le premier ou le dernier point où une propriété monotone devient vraie.
Limite importante. Le tri des données est une précondition. Si les données changent continuellement, maintenir leur ordre peut coûter plus cher que le gain obtenu lors des recherches.
3. Tri fusion
Objectif. Trier une suite avec un temps prévisible tout en conservant l’ordre relatif des éléments équivalents.
Idée fondamentale. On divise la suite en deux moitiés, on trie récursivement chacune d’elles, puis on les fusionne en comparant chaque fois les premiers éléments qui n’ont pas encore été copiés.
Pseudo-code
TRI_FUSION(A)
SI longueur(A) ≤ 1 RENVOYER A
milieu ← partie_entiere(longueur(A) / 2)
gauche ← TRI_FUSION(A[0 ... milieu−1])
droite ← TRI_FUSION(A[milieu ... fin])
RENVOYER FUSIONNER(gauche, droite)
FUSIONNER(G, D)
resultat ← suite vide
TANT_QUE G et D ne sont pas vides
déplacer le plus petit premier élément dans resultat
ajouter tous les éléments restants
RENVOYER resultatExemple détaillé. [8, 3, 5, 1] est partagé en [8,3] et [5,1]. Les moitiés deviennent [3,8] et [1,5] ; leur fusion donne [1,3,5,8].
Complexité. Temps O(n log n) dans les meilleurs, moyens et pires cas ; mémoire auxiliaire habituelle O(n). Le tri est stable si, en cas d’égalité, on choisit d’abord l’élément de gauche.
Quand l’utiliser. Lorsque des performances prévisibles et la stabilité sont nécessaires, sur des listes chaînées ou pour le tri externe de données trop volumineuses pour la mémoire.
Limite importante. Sur un tableau, il utilise de la mémoire supplémentaire ; pour de très petits blocs, un tri plus simple peut avoir de meilleures constantes.
4. Tri rapide (quicksort)
Objectif. Trier rapidement en mémoire au moyen d’un partitionnement effectué sur place.
Idée fondamentale. On choisit un pivot, on place avant lui les éléments qui ne sont pas plus grands et après lui les éléments plus grands, puis on trie récursivement les deux parties. Un pivot aléatoire réduit le risque de partitions constamment déséquilibrées.
Pseudo-code
TRI_RAPIDE(A, bas, haut)
SI bas ≥ haut RENVOYER
p ← PARTITION_ALEATOIRE(A, bas, haut)
TRI_RAPIDE(A, bas, p − 1)
TRI_RAPIDE(A, p + 1, haut)
PARTITION_ALEATOIRE place un pivot aléatoire à sa
position définitive et renvoie son indiceExemple détaillé. Avec le pivot 5, [8,3,5,1,7] est conceptuellement partagé en [3,1] + [5] + [8,7]. Le tri des deux parties donne [1,3,5,7,8].
Complexité. Temps espéré O(n log n), pire cas O(n²). Le partitionnement peut s’effectuer sur place ; la pile occupe en moyenne O(log n), mais peut atteindre O(n).
Quand l’utiliser. Pour des tableaux en mémoire lorsque comptent la vitesse moyenne, la localité du cache et une faible mémoire auxiliaire. Les bibliothèques emploient souvent des variantes hybrides.
Limite importante. Il n’est normalement pas stable et de mauvais pivots répétés provoquent le comportement quadratique. Dans une application, il vaut mieux utiliser la fonction de tri de la bibliothèque.
5. Parcours en largeur (BFS)
Objectif. Parcourir un graphe par niveaux et trouver depuis une source un chemin comportant le moins d’arêtes.
Idée fondamentale. Une file conserve les sommets découverts mais pas encore explorés. Tous les sommets à distance d sont traités avant ceux à distance d + 1.
Pseudo-code
BFS(G, source)
pour chaque sommet v : visite[v] ← faux
visite[source] ← vrai
distance[source] ← 0
FILE.ajouter(source)
TANT_QUE FILE n’est pas vide
u ← FILE.retirer_premier()
POUR chaque v adjacent à u
SI non visite[v]
visite[v] ← vrai
distance[v] ← distance[u] + 1
parent[v] ← u
FILE.ajouter(v)Exemple détaillé. Si A est relié à B et C, B à D et C à E, le parcours depuis A visite d’abord A, puis B et C, enfin D et E. Le tableau des parents permet de reconstruire un chemin minimal.
Complexité. Avec des listes d’adjacence, temps O(V+E) et mémoire de travail O(V), en plus du graphe.
Quand l’utiliser. Pour les distances dans un graphe non pondéré, les degrés de séparation, la propagation par niveaux, les labyrinthes dont toutes les actions ont le même coût et le test de bipartition.
Limite importante. Il ne minimise pas le coût lorsque les arêtes ont des poids différents ; l’ordre entre sommets du même niveau dépend de l’ordre des adjacences.
6. Parcours en profondeur (DFS)
Objectif. Explorer complètement une branche avant de revenir en arrière et d’essayer les autres possibilités.
Idée fondamentale. Une pile, explicite ou fournie par la récursion, mémorise le chemin courant. Lorsqu’un sommet ne possède plus de nouveau voisin, le parcours revient au sommet précédent.
Pseudo-code
DFS(G, source)
visite[source] ← vrai
PILE ← [source]
TANT_QUE PILE n’est pas vide
u ← PILE.retirer_dernier()
TRAITER(u)
POUR chaque v adjacent à u
SI non visite[v]
visite[v] ← vrai
parent[v] ← u
PILE.ajouter(v)Exemple détaillé. Dans le graphe A–B, A–C, B–D et C–E, un parcours possible visite A, B, D, revient à A, puis poursuit avec C, E. Un autre ordre des voisins donne un autre parcours valide.
Complexité. Avec des listes d’adjacence, temps O(V+E) et mémoire O(V). Une récursion très profonde peut épuiser la pile d’appels du langage.
Quand l’utiliser. Pour les composantes connexes, la détection de cycles, le tri topologique des graphes acycliques, l’exploration de labyrinthes et les problèmes de retour sur trace.
Limite importante. Il ne garantit pas le chemin le plus court. Dans un graphe, les sommets doivent être marqués comme visités afin d’éviter les cycles infinis.
7. Algorithme de Dijkstra
Objectif. Calculer les distances minimales depuis une source dans un graphe dont les poids sont non négatifs.
Idée fondamentale. On conserve une distance provisoire pour chaque sommet. Une file de priorité extrait le sommet non fixé le plus proche ; relâcher une arête consiste à vérifier si passer par ce sommet permet d’atteindre son voisin à moindre coût.
Pseudo-code
DIJKSTRA(G, source)
pour chaque v : distance[v] ← infini
distance[source] ← 0
FILE_PRIORITE.ajouter(0, source)
TANT_QUE la file n’est pas vide
(du, u) ← extraire_minimum()
SI du ≠ distance[u] CONTINUER
POUR chaque arête (u, v, poids)
candidat ← du + poids
SI candidat < distance[v]
distance[v] ← candidat
parent[v] ← u
ajouter(candidat, v)Exemple détaillé. Avec les arêtes A–B:4, A–C:1, C–B:2, B–D:1 et C–D:5, le plus court chemin de A à D est A–C–B–D, de coût 4.
Complexité. Avec des listes d’adjacence et un tas binaire, le temps est O((V+E) log V). Distances et parents occupent O(V) ; dans la variante simple présentée, les anciennes entrées du tas peuvent occuper jusqu’à O(E), en plus du graphe O(V+E).
Quand l’utiliser. Pour les réseaux routiers sans coûts négatifs, le routage, les dépendances pondérées et tout problème réductible à des plus courts chemins pondérés non négatifs.
Limite importante. Une seule arête négative invalide la garantie. Il faut alors un algorithme tel que Bellman–Ford ; lorsque tous les poids sont égaux, BFS suffit.
8. Sac à dos 0/1 par programmation dynamique
Objectif. Choisir des objets indivisibles afin de maximiser la valeur sans dépasser une capacité entière.
Idée fondamentale. Des choix différents réutilisent les mêmes sous-problèmes. dp[c] conserve la meilleure valeur possible pour une capacité c. Pour chaque objet, les capacités sont parcourues en ordre décroissant afin de ne pas reprendre le même objet.
Pseudo-code
SAC_A_DOS_01(objets, W)
dp[0 ... W] ← 0
POUR chaque (poids, valeur) dans objets
POUR c DE W À poids, EN ORDRE DECROISSANT
dp[c] ← maximum(dp[c], dp[c − poids] + valeur)
RENVOYER dp[W]Exemple détaillé. Avec une capacité de 5 et les objets (poids 2, valeur 3), (3,4) et (4,5), les deux premiers remplissent le sac et donnent la valeur 7, supérieure à celle de tout objet seul.
Complexité. Temps O(nW) et mémoire O(W). Cette complexité est pseudo-polynomiale : elle dépend de la valeur numérique de W, pas seulement du nombre de chiffres qui l’écrivent.
Quand l’utiliser. Pour des budgets ou capacités entiers modérés, la sélection de projets et l’allocation de ressources lorsque chaque choix ne peut être retenu qu’une fois.
Limite importante. Avec une capacité énorme, le tableau devient impraticable ; le modèle simple ne représente pas non plus les dépendances entre objets ni les valeurs non additives.
9. Knuth–Morris–Pratt (KMP)
Objectif. Trouver toutes les occurrences exactes d’un motif dans un texte sans revenir en arrière dans le texte.
Idée fondamentale. Une table des préfixes indique, à chaque position du motif, la longueur du plus long préfixe qui est aussi un suffixe. Après une différence, cette information est réutilisée au lieu de repartir de zéro.
Pseudo-code
CONSTRUIRE_PREFIXES(P)
prefixe[0] ← 0; j ← 0
POUR i DE 1 À longueur(P) − 1
TANT_QUE j > 0 ET P[i] ≠ P[j]
j ← prefixe[j − 1]
SI P[i] = P[j] ALORS j ← j + 1
prefixe[i] ← j
RENVOYER prefixe
KMP(texte T, motif P)
prefixe ← CONSTRUIRE_PREFIXES(P); j ← 0
POUR i DE 0 À longueur(T) − 1
TANT_QUE j > 0 ET T[i] ≠ P[j]
j ← prefixe[j − 1]
SI T[i] = P[j] ALORS j ← j + 1
SI j = longueur(P)
SIGNALER i − longueur(P) + 1
j ← prefixe[j − 1]Exemple détaillé. En cherchant ABABAC dans ABABABAC, après une différence KMP sait que le suffixe ABAB est aussi un préfixe utile. Il trouve l’occurrence qui commence à l’indice 2, en comptant depuis zéro.
Complexité. La construction de la table et la recherche prennent ensemble O(n+m) ; la table utilise O(m) mémoire.
Quand l’utiliser. Pour la recherche exacte dans de longs textes ou des flux, surtout si le motif contient de nombreuses répétitions et si une garantie linéaire est utile.
Limite importante. Il cherche des correspondances exactes, et non des ressemblances. Le pseudo-code suppose un motif non vide ; pour une seule recherche courte, la fonction optimisée du langage est normalement préférable.
10. Codage de Huffman
Objectif. Attribuer des codes binaires courts aux symboles fréquents et plus longs aux symboles rares, tout en garantissant un décodage unique.
Idée fondamentale. On place les fréquences dans une file de priorité et on fusionne à plusieurs reprises les deux nœuds les moins fréquents. Les chemins gauche et droite de l’arbre obtenu forment un code préfixe : aucun code n’est le préfixe d’un autre.
Pseudo-code
HUFFMAN(frequences)
Q ← tas_minimum avec une feuille par symbole
TANT_QUE taille(Q) > 1
x ← Q.extraire_minimum()
y ← Q.extraire_minimum()
z ← noeud(frequence(x) + frequence(y), x, y)
Q.ajouter(z)
RENVOYER Q.extraire_minimum()Exemple détaillé. Avec les fréquences A:5, B:2, C:1, D:1, un code possible est A=0, B=10, C=110, D=111. Les 9 symboles nécessitent 15 bits, contre 18 bits avec un code fixe de deux bits.
Complexité. Pour k symboles distincts, construire l’arbre coûte O(k log k) ; coder ou décoder un message coûte O(L). L’arbre et la table occupent O(k).
Quand l’utiliser. Comme composant de formats de compression et lorsque des fréquences fiables sont connues. Il est optimal parmi les codes préfixes qui attribuent un nombre entier de bits à chaque symbole.
Limite importante. À lui seul, il n’exploite ni les longues répétitions ni le contexte ; sur un petit fichier, le stockage de l’arbre peut annuler le gain. Pour des données réelles, il faut utiliser des formats et bibliothèques standard.
Quel algorithme choisir ?
Ce tableau ne remplace pas l’analyse des contraintes, mais fournit un premier repère.
| Problème | Premier choix | Raison |
|---|---|---|
| Plus grand commun diviseur et nombres premiers entre eux | Algorithme d’Euclide | Il réduit rapidement la paire grâce aux restes. |
| Valeur dans une suite triée | Recherche dichotomique | Elle élimine la moitié de l’intervalle à chaque comparaison. |
| Tri stable et prévisible | Tri fusion | Il garantit toujours un temps proportionnel à n log n. |
| Tri rapide d’un tableau en mémoire | Tri rapide (quicksort) | Il offre d’excellentes performances moyennes et un partitionnement sur place. |
| Plus court chemin dans un graphe non pondéré | Parcours en largeur (BFS) | Le parcours par niveaux garantit le plus petit nombre d’arêtes. |
| Exploration complète, cycles ou retour sur trace | Parcours en profondeur (DFS) | Il suit une branche jusqu’au bout avant de revenir aux alternatives. |
| Plus court chemin avec poids non négatifs | Algorithme de Dijkstra | Il fixe toujours la plus petite distance provisoire. |
| Sélection optimale avec capacité entière modérée | Sac à dos 0/1 par programmation dynamique | Il réutilise les résultats de sous-problèmes qui se recouvrent. |
| Recherche exacte d’un motif dans un texte | Knuth–Morris–Pratt (KMP) | Il ne réexamine pas des caractères dont l’information est déjà connue. |
| Code préfixe fondé sur les fréquences | Codage de Huffman | Il attribue moins de bits aux symboles les plus fréquents. |
La comparaison de ces algorithmes révèle une leçon générale : il faut d’abord définir précisément l’entrée, le résultat attendu et les contraintes, puis choisir l’idée qui exploite le mieux la structure du problème. La correction et les préconditions passent avant la vitesse.