Complexité algorithmique #

La plupart des problèmes ne sont pas fondamentalement difficiles, mais toutes les solutions ne sont pas également efficaces. La complexité algorithmique fournit une mesure de cette efficacité.

La complexité algorithmique mesure le temps ou la mémoire qu’un algorithme nécessite en fonction de la taille de l’entrée (souvent notée \( n \)). Pour comparer les algorithmes, on utilise la notation grand-O (ou O-grande), qui donne un ordre de grandeur du nombre d’opérations à effectuer lorsque la taille des données augmente.

Comprendre la complexité algorithmique permet de choisir ou d’inventer des solutions efficaces, surtout pour de grandes quantités de données. Il est souvent utile de commencer par une solution simple (même lente), puis de chercher à l’optimiser en utilisant des structures de données ou des propriétés mathématiques adaptées.

Dans ce cours, vous n’avez pas à maîtriser la notation grand-O et la complexité algorithmique. Néanmoins, il est utile d’être familier avec les principales notions.

Notation grand-O #

La notation \( O(f(n)) \) signifie que, pour des entrées de taille \( n \), l’algorithme effectue au plus un nombre d’opérations proportionnel à \( f(n) \) (à une constante près). On ne s’intéresse qu’au comportement pour de grandes valeurs de \( n \), et on ignore les détails d’implémentation ou les constantes cachées.

On considère souvent que l’accès à un élément d’un tableau par son index a une complexité \( O(1) \) puisqu’il s’agit d’une seule opération. Les opérations arithmétiques (+, -, etc.) ont aussi une complexité \( O(1) \).

Cette notation permet également de comparer différentes classes de complexité. Une hiérarchie courante observe que les algorithmes en complexité constante sont les plus efficaces pour de grandes entrées, suivis de ceux en complexité logarithmique (\(O(\log n)\)), puis linéaire (\(O(n)\)), linéarithmique (\(O(n\log n)\)), et enfin quadratique (\(O(n^2)\)). Formellement, cela se traduit par des inclusions entre les classes : \( O(1) \subseteq O(\log n) \subseteq O(n) \subseteq O(n \log n) \subseteq O(n^2) \), où le logarithme est pris en base quelconque supérieure à 1 (la base n’affecte la définition qu’à une constante multiplicative près).

Pour établir ces inclusions, rappelons la définition : une fonction \( g(n) \) appartient à \( O(f(n)) \) s’il existe une constante positive \( c \) et un entier \( n_0 \) tels que, pour tout \( n \geq n_0 \), \( g(n) \leq c \cdot f(n) \) (en considérant des fonctions positives pour \( n \) grand).

Considérons le logarithme en base 2 pour les preuves explicites, sans perte de généralité.

Pour \( O(1) \subseteq O(\log n) \) : toute fonction constante, disons \( g(n) = k \), satisfait l’inclusion. Comme \( \log_2 n \to \infty \) lorsque \( n \to \infty \), il existe \( n_0 \) tel que \( \log_2 n \geq k \) pour \( n \geq n_0 \). Ainsi, avec \( c = 1 \), \( k \leq \log_2 n \) pour \( n \geq n_0 \).

Pour \( O(\log n) \subseteq O(n) \) : prenons \( g(n) = \log_2 n \). Il est clair que \( \log_2 n \leq n \) pour tout \( n \geq 1 \) (vérifiable pour petits \( n \), et évident asymptotiquement puisque la fonction exponentielle croît plus vite). Plus précisément, le limite \( \frac{\log_2 n}{n} \to 0 \) quand \( n \to \infty \) implique l’existence de \( c = 1 \) et \( n_0 = 1 \) tels que \( \log_2 n \leq n \).

Pour \( O(n) \subseteq O(n \log n) \) : pour \( g(n) = n \), observons que \( \log_2 n \geq 1 \) pour \( n \geq 2 \). Donc \( n \leq n \cdot \log_2 n \) pour \( n \geq 2 \), avec \( c = 1 \) et \( n_0 = 2 \).

Pour \( O(n \log n) \subseteq O(n^2) \) : pour \( g(n) = n \log_2 n \), notons que \( \log_2 n \leq n \) pour \( n \geq 1 \) (comme ci-dessus). Il suit que \( n \log_2 n \leq n \cdot n = n^2 \), avec \( c = 1 \) et \( n_0 = 1 \).

Utilisez l’application suivante pour comprendre la différence entre \(\log n\), \(n\), \(n \log n\) et \(n^2\). Assurez-vous d’avoir une bonne intuition concernant la forme de ces fonctions.

Exemples d’algorithmes linéaires #

Un algorithme est en \( O(n) \) si le nombre d’opérations croît linéairement avec la taille de l’entrée. Par exemple, parcourir un tableau pour calculer la somme de ses éléments :

somme = 0
POUR i de 0 à n-1
    somme = somme + tableau[i]
FIN POUR

Une variable somme est initialisée à 0 pour accumuler le résultat. La boucle (POUR i de 0 à n-1) parcourt chaque indice i du tableau, et à chaque itération, la valeur de l’élément tableau[i] est ajoutée à somme (somme = somme + tableau[i]). À la fin de la boucle, somme contient la somme totale des éléments du tableau.

Ici, chaque élément est visité une seule fois, donc le temps d’exécution est proportionnel à \( n \).

Un autre exemple classique consiste à chercher la valeur maximale dans un tableau :

maximum = tableau[0]
POUR i de 1 à n-1
    SI tableau[i] > maximum
        maximum = tableau[i]
    FIN SI
FIN POUR

On commence par supposer que le premier élément est le plus grand. Ensuite, on parcourt le reste du tableau une seule fois et on met à jour la variable maximum lorsqu’on trouve une valeur plus grande. Ici encore, chaque élément est examiné une seule fois, donc la complexité est en \( O(n) \).

On peut aussi compter combien d’éléments satisfont une certaine condition, par exemple combien de notes sont supérieures ou égales à 60 :

compteur = 0
POUR i de 0 à n-1
    SI notes[i] ≥ 60
        compteur = compteur + 1
    FIN SI
FIN POUR

Dans cet exemple, on ne fait qu’un seul parcours du tableau. Même s’il y a un test à chaque itération, le nombre total d’opérations reste proportionnel à \( n \).

Exemples d’algorithmes quadratiques #

Un algorithme est en \( O(n^2) \) si le nombre d’opérations croît comme le carré de la taille de l’entrée. C’est typique des algorithmes qui utilisent deux boucles imbriquées, comme la recherche de toutes les paires d’éléments dans un tableau :

POUR i de 0 à n-1
    POUR j de 0 à n-1
        faire quelque chose avec tableau[i] et tableau[j]
    FIN POUR
FIN POUR

Ce pseudocode décrit une double boucle imbriquée qui parcourt toutes les paires possibles d’éléments dans un tableau de taille n. La boucle externe (POUR i de 0 à n-1) itère sur chaque indice i du tableau, tandis que la boucle interne (POUR j de 0 à n-1) parcourt à nouveau tous les indices j du tableau, indépendamment de i. À chaque itération, une opération (désignée par « faire quelque chose ») est effectuée en utilisant les éléments tableau[i] et tableau[j]. Cela inclut les cas où i et j désignent le même élément (quand i = j) ainsi que toutes les combinaisons de paires, y compris les permutations (par exemple, (i,j) et (j,i)).

Ici, pour chaque valeur de \( i \), on parcourt toutes les valeurs de \( j \), ce qui donne \( n \times n = n^2 \) opérations.

Un autre exemple quadratique consiste à vérifier s’il existe deux éléments égaux dans un tableau, sans utiliser de structure de données supplémentaire :

POUR i de 0 à n-1
    POUR j de i+1 à n-1
        SI tableau[i] == tableau[j]
            retourner VRAI
        FIN SI
    FIN POUR
FIN POUR
retourner FAUX

Ici, chaque élément est comparé avec presque tous les éléments qui le suivent. Lorsque \( n \) est grand, le nombre total de comparaisons est proportionnel à \( n^2 \).

On retrouve aussi une complexité quadratique lorsqu’on parcourt toutes les cases d’une grille carrée de taille \( n \times n \) :

POUR ligne de 0 à n-1
    POUR colonne de 0 à n-1
        traiter grille[ligne][colonne]
    FIN POUR
FIN POUR

La boucle externe s’exécute \( n \) fois, et pour chaque ligne, la boucle interne s’exécute aussi \( n \) fois. On traite donc \( n^2 \) cases au total.

Un algorithme \( O(n^2) \) est plus lent qu’un algorithme \( O(n) \) quand \( n \) est très grand.

Recherche dans un tableau trié #

Lorsqu’un tableau est trié, on peut utiliser la recherche dichotomique (ou recherche binaire) pour trouver rapidement un élément. Cette méthode consiste à comparer la valeur recherchée à l’élément du milieu du tableau : si la valeur est plus petite, on recommence la recherche dans la moitié gauche ; sinon, dans la moitié droite. On répète jusqu’à trouver l’élément ou à épuiser le tableau.

Voici un exemple de pseudocode pour la recherche binaire :

DEBUT
    debut ← 0
    fin ← n - 1
    TANT QUE debut ≤ fin
        milieu ← (debut + fin) // 2
        SI tableau[milieu] == valeur
            retourner VRAI
        SINON SI tableau[milieu] < valeur
            debut ← milieu + 1
        SINON
            fin ← milieu - 1
        FIN SI
    FIN TANT QUE
    retourner FAUX
FIN

Le pseudocode décrit ce processus : on initialise deux indices, debut (0) et fin (n-1), délimitant la partie du tableau à explorer. À chaque itération, on calcule l’indice milieu (moyenne de debut et fin) et compare l’élément à cet indice (tableau[milieu]) avec la valeur recherchée. Si les deux sont égaux, l’élément est trouvé (retourner VRAI). Si la valeur est plus grande, la recherche se poursuit dans la moitié droite en ajustant debut à milieu + 1 ; sinon, dans la moitié gauche en ajustant fin à milieu - 1. Le processus se répète tant que debut ≤ fin. Si l’intervalle est épuisé sans trouver la valeur, l’algorithme retourne FAUX, indiquant que l’élément n’est pas dans le tableau.

Pour mieux comprendre l’algorithme, essayez de chercher des nombres dans un tableau trié avec l’application suivante.

Observez comment vous faites toujours moins de recherche qu’il y a d’éléments dans le tableau. Pouvez-vous faire en sorte qu’une seule étape soit nécessaire ? Quel est le nombre maximal d’étapes nécessaires ?

Cet algorithme a une complexité en \( O(\log n) \), ce qui le rend très efficace pour les grands tableaux triés. Cela signifie que le nombre d’opérations nécessaires pour trouver (ou ne pas trouver) un élément ne croît pas proportionnellement à la taille du tableau, mais beaucoup plus lentement. Par exemple, pour un tableau de 1 000 000 d’éléments, la recherche binaire nécessite au maximum environ 20 comparaisons (car \( \log_2 1\,000\,000 \approx 20 \)), alors qu’une recherche linéaire pourrait en demander jusqu’à 1 000 000 dans le pire cas. Plus le tableau est grand, plus l’avantage de la recherche binaire est important.

À chaque étape de la recherche binaire, on divise le nombre d’éléments restants par deux. Si on commence avec \( n \) éléments, après une comparaison il en reste \( n/2 \), puis \( n/4 \), puis \( n/8 \), etc. On répète ce processus jusqu’à ce qu’il ne reste qu’un seul élément à examiner.

On cherche donc le nombre d’étapes \( k \) tel que :

En résolvant pour \( k \) :

Ainsi, le nombre maximal de comparaisons est proportionnel à \( \log_2 n \). C’est pourquoi on dit que la recherche binaire a une complexité en \( O(\log n) \).

Recherche d’une chaîne de caractères #

Un autre problème très courant est la recherche d’une sous-chaîne : étant donné un texte \( t \) de longueur \( n \) et un motif \( x \) de longueur \( m \) (avec \( m \leq n \)), on veut savoir si le motif apparaît dans le texte, et à quelle position. C’est exactement ce que fait la méthode indexOf en Java :

String texte = "le chat dort";
System.out.println(texte.indexOf("chat")); // Affiche 3

Algorithme naïf #

L’idée la plus simple consiste à essayer chaque position de départ possible dans le texte, et à comparer les caractères un à un jusqu’à trouver une différence.

FONCTION rechercheNaive(t, x)
    n ← longueur(t)
    m ← longueur(x)
    POUR pos de 0 à n - m
        i ← 0
        TANT QUE i < m ET x[i] == t[pos + i]
            i ← i + 1
        FIN TANT QUE
        SI i == m ALORS
            retourner pos
        FIN SI
    FIN POUR
    retourner -1
FIN FONCTION

La boucle externe (pos de 0 à n-m) choisit une position de départ dans le texte, c’est-à-dire l’endroit où l’on tente d’aligner le motif. La boucle interne compare le motif au texte, caractère par caractère, à partir de cette position : tant que les caractères coïncident (x[i] == t[pos + i]), on avance l’indice i. Si l’on parvient à comparer les \( m \) caractères du motif (i == m), c’est que le motif apparaît à la position pos et on la retourne. Sinon, on abandonne cet alignement et on recommence une position plus loin. Si aucune position ne fonctionne, la fonction retourne -1.

Sur des textes ordinaires (par exemple, chercher un mot français dans un roman), cet algorithme est très rapide : la première ou la deuxième comparaison échoue presque toujours, et le coût est en pratique proche de \( O(n) \).

Un cas qui dégénère #

Le pire cas de l’algorithme naïf est en \( O(n \times m) \). Pour le voir, il suffit de prendre un texte et un motif composés presque uniquement du même caractère. Cherchons le motif

dans le texte

À chaque position de départ, l’algorithme naïf compare avec succès les \( m-1 \) premiers caractères (des a), puis échoue sur le dernier caractère (le b du motif contre un a du texte). Il a donc fait \( m \) comparaisons pour n’avancer que d’une seule position. Comme il y a \( n - m + 1 \) positions, le nombre total de comparaisons est d’environ \( (n-m+1) \times m \), donc de l’ordre de \( n \times m \).

Prenons un exemple concret avec t = "aaaaaaaa" (\( n = 8 \)) et x = "aaab" (\( m = 4 \)) :

Soit 20 comparaisons pour un texte de 8 caractères. Avec un texte d’un million de a et un motif de mille caractères, on ferait environ un milliard de comparaisons alors que la réponse est simplement « absent ». Le problème vient du fait que l’algorithme naïf oublie tout ce qu’il vient d’apprendre : après avoir constaté que les caractères aux positions 0 à \( m-2 \) sont des a, il recommence à zéro une position plus loin.

Les algorithmes qui suivent corrigent ce défaut de deux manières différentes. Les uns (Knuth-Morris-Pratt, two-way) exploitent la structure du motif pour ne jamais recomparer un caractère du texte inutilement, ce qui garantit un temps linéaire. Les autres (Boyer-Moore, Horspool) comparent le motif de droite à gauche, ce qui leur permet de sauter des portions entières du texte sans même les regarder. Dans ce qui suit, on note \( \Sigma \) l’alphabet utilisé (par exemple les 128 caractères ASCII) et \( |\Sigma| \) sa taille.

L’algorithme de Knuth-Morris-Pratt #

L’algorithme de Knuth-Morris-Pratt (1977), souvent abrégé en KMP, part de l’observation suivante : quand une comparaison échoue, on connaît déjà les caractères du texte qui viennent d’être vérifiés, puisqu’ils sont égaux à un préfixe du motif. Il est donc inutile de les relire.

La table des bords #

Un bord d’une chaîne est un préfixe qui est aussi un suffixe, sans être la chaîne entière. Par exemple, "abcab" a pour bord "ab" (de longueur 2). L’algorithme calcule, pour chaque préfixe du motif, la longueur de son plus long bord.

FONCTION tableBords(x)
    m ← longueur(x)
    bord ← nouveau tableau de taille m + 1
    bord[0] ← -1
    i ← 0
    j ← -1
    TANT QUE i < m
        TANT QUE j ≥ 0 ET x[i] ≠ x[j]
            j ← bord[j]
        FIN TANT QUE
        i ← i + 1
        j ← j + 1
        bord[i] ← j
    FIN TANT QUE
    retourner bord
FIN FONCTION

Pour le motif x = "aaab", on obtient :

La recherche #

La recherche parcourt le texte une seule fois. L’indice i (position dans le texte) n’est jamais diminué : en cas d’échec, c’est l’indice j (position dans le motif) qui recule, grâce à la table des bords.

FONCTION rechercheKMP(t, x)
    n ← longueur(t)
    m ← longueur(x)
    bord ← tableBords(x)
    i ← 0          // position dans le texte
    j ← 0          // position dans le motif
    TANT QUE i < n
        TANT QUE j ≥ 0 ET t[i] ≠ x[j]
            j ← bord[j]        // on glisse le motif sans reculer dans le texte
        FIN TANT QUE
        i ← i + 1
        j ← j + 1
        SI j == m ALORS
            retourner i - m    // motif trouvé
        FIN SI
    FIN TANT QUE
    retourner -1
FIN FONCTION

Reprenons t = "aaaaaaaa" et x = "aaab". Après avoir aligné "aaa" sur les trois premiers caractères, la comparaison de x[3] = 'b' avec t[3] = 'a' échoue. Au lieu de tout recommencer, l’algorithme pose j ← bord[3] = 2 : il sait déjà que t[1..2] = "aa" correspond au préfixe "aa" du motif. Il ne lui reste qu’à comparer t[3] avec x[2] = 'a', ce qui réussit. Chaque caractère du texte est donc examiné au plus deux fois, et le total est d’environ \( 2n \) comparaisons au lieu de \( n \times m \).

Complexité #

La construction de la table demande \( O(m) \) opérations, et la recherche \( O(n) \), soit \( O(n + m) \) au total, dans le pire cas. L’argument est le suivant : à chaque tour de la boucle principale, soit i augmente de 1 (au plus \( n \) fois), soit j diminue d’au moins 1. Or j n’augmente que lorsque i augmente, donc j ne peut pas diminuer plus de \( n \) fois. Le nombre total d’opérations est donc borné par \( 2n \).

L’algorithme utilise \( O(m) \) mémoire supplémentaire pour la table des bords, et il ne dépend pas de la taille de l’alphabet. En revanche, il examine tous les caractères du texte : il n’est jamais plus rapide que \( n \) comparaisons, même dans le meilleur cas.

L’algorithme de Boyer-Moore #

L’algorithme de Boyer-Moore (1977) adopte une stratégie opposée : il aligne le motif sur le texte, puis compare de droite à gauche, en commençant par le dernier caractère du motif. L’intérêt est qu’un échec sur le dernier caractère permet souvent de faire un très grand saut, sans jamais regarder les caractères sautés.

La règle du mauvais caractère #

Supposons que la comparaison échoue à la position j du motif, face au caractère c = t[pos + j] du texte. Deux cas se présentent :

• si c n’apparaît nulle part dans le motif, aucun alignement chevauchant cette position ne peut réussir : on peut décaler le motif de j + 1 positions d’un seul coup ;
• si c apparaît dans le motif, on décale le motif juste assez pour aligner la dernière occurrence de c avec ce caractère du texte.

On précalcule pour cela la position de la dernière occurrence de chaque caractère de l’alphabet dans le motif.

FONCTION tableDernier(x)
    m ← longueur(x)
    POUR chaque caractère c de l’alphabet
        dernier[c] ← -1
    FIN POUR
    POUR i de 0 à m - 1
        dernier[x[i]] ← i
    FIN POUR
    retourner dernier
FIN FONCTION

Le décalage vaut alors max(1, j - dernier[c]). Le max avec 1 est indispensable : si la dernière occurrence de c se trouve à droite de la position j, la formule donnerait un décalage négatif, c’est-à-dire un recul.

La règle du bon suffixe #

La deuxième règle exploite les caractères qui, eux, ont correspondu. Si le suffixe x[j+1 .. m-1] a été apparié avant l’échec, on cherche une autre occurrence de ce même suffixe ailleurs dans le motif, et on décale pour l’aligner. À défaut, on cherche le plus long préfixe du motif qui soit aussi un suffixe du bon suffixe.

Prenons x = "batabat". Supposons que le suffixe "bat" (positions 4 à 6) ait correspondu, mais que la comparaison échoue à la position 3. Comme "bat" apparaît aussi aux positions 0 à 2, on décale le motif de 4 positions pour aligner cette autre occurrence avec le "bat" du texte :

texte  : . . . . b a t . . .
motif  : b a t a b a t          (échec à la position 3)
motif  :         b a t a b a t  (après un décalage de 4)

Ces tables se calculent en \( O(m) \) opérations et occupent \( O(m) \) mémoire.

La recherche #

À chaque échec, l’algorithme applique le plus grand des deux décalages.

FONCTION rechercheBoyerMoore(t, x)
    n ← longueur(t)
    m ← longueur(x)
    dernier ← tableDernier(x)
    suffixe ← tableBonSuffixe(x)
    pos ← 0
    TANT QUE pos + m ≤ n
        j ← m - 1
        TANT QUE j ≥ 0 ET x[j] == t[pos + j]
            j ← j - 1            // comparaison de droite à gauche
        FIN TANT QUE
        SI j < 0 ALORS
            retourner pos        // motif trouvé
        FIN SI
        pos ← pos + max(j - dernier[t[pos + j]], suffixe[j])
    FIN TANT QUE
    retourner -1
FIN FONCTION

Complexité #

Le prétraitement est en \( O(m + |\Sigma|) \), et la mémoire supplémentaire en \( O(m + |\Sigma|) \).

Dans le meilleur cas, l’algorithme est sous-linéaire : il ne lit qu’un caractère du texte sur \( m \). Par exemple, en cherchant "abcdefgh" dans un texte composé uniquement de z, chaque alignement échoue dès la première comparaison et le motif saute de \( m \) positions : environ \( n/m \) comparaisons suffisent. Aucun algorithme qui lirait tout le texte ne peut faire cela. C’est la raison pour laquelle Boyer-Moore et ses variantes sont si utilisés en pratique, notamment par les outils de recherche dans les fichiers.

Dans le pire cas, la version complète (avec la règle du bon suffixe) trouve la première occurrence en \( O(n) \) : on peut montrer qu’elle effectue au plus \( 3n \) comparaisons. Si l’on n’utilise que la règle du mauvais caractère, en revanche, le pire cas retombe à \( O(n \times m) \), comme pour l’algorithme naïf.

L’algorithme de Horspool #

L’algorithme de Horspool (1980) est une simplification de Boyer-Moore. Il abandonne la règle du bon suffixe, plus délicate à programmer, et modifie légèrement la règle du mauvais caractère : quel que soit l’endroit où la comparaison a échoué, le décalage est déterminé par le caractère du texte aligné avec le dernier caractère du motif.

La table de décalage se calcule à partir des \( m-1 \) premiers caractères du motif (on exclut le dernier, sinon le décalage serait toujours nul) :

FONCTION tableHorspool(x)
    m ← longueur(x)
    POUR chaque caractère c de l’alphabet
        decalage[c] ← m
    FIN POUR
    POUR i de 0 à m - 2
        decalage[x[i]] ← m - 1 - i
    FIN POUR
    retourner decalage
FIN FONCTION

FONCTION rechercheHorspool(t, x)
    n ← longueur(t)
    m ← longueur(x)
    decalage ← tableHorspool(x)
    pos ← 0
    TANT QUE pos + m ≤ n
        j ← m - 1
        TANT QUE j ≥ 0 ET x[j] == t[pos + j]
            j ← j - 1
        FIN TANT QUE
        SI j < 0 ALORS
            retourner pos
        FIN SI
        pos ← pos + decalage[t[pos + m - 1]]
    FIN TANT QUE
    retourner -1
FIN FONCTION

Cherchons x = "chat" dans t = "le chat dort". La table vaut decalage['c'] = 3, decalage['h'] = 2, decalage['a'] = 1, et \( 4 \) pour tous les autres caractères.

Cinq comparaisons pour un texte de douze caractères, alors que l’algorithme naïf en aurait fait huit. L’écart grandit avec la taille du texte et du motif.

Complexité #

Le prétraitement est en \( O(m + |\Sigma|) \) et la mémoire supplémentaire en \( O(|\Sigma|) \), c’est-à-dire une taille fixe indépendante du motif.

En moyenne, sur un texte « ordinaire » écrit sur un grand alphabet, Horspool est proche du meilleur cas de Boyer-Moore et fait environ \( n/m \) comparaisons. Sa simplicité en fait souvent le plus rapide des algorithmes classiques en pratique.

Mais son pire cas reste en \( O(n \times m) \), puisqu’il ne conserve aucune mémoire des comparaisons réussies. Il suffit de chercher x = "baaa" dans un texte composé uniquement de a : à chaque alignement, les trois a du motif correspondent, le b échoue, et le décalage vaut decalage['a'] = 1. On fait donc \( m \) comparaisons pour avancer d’une seule position, exactement comme l’algorithme naïf.

L’algorithme two-way #

L’algorithme two-way (ou algorithme de Crochemore-Perrin, 1991) offre le meilleur des deux mondes. Comme Knuth-Morris-Pratt, il trouve le motif en temps \( O(n + m) \) dans le pire cas ; mais il n’utilise qu’une quantité constante de mémoire supplémentaire (\( O(1) \)), là où Knuth-Morris-Pratt construit une table de taille \( m \) et où Boyer-Moore et Horspool ont besoin d’une table indexée par l’alphabet. C’est l’algorithme utilisé par les fonctions strstr et memmem de la bibliothèque C standard (glibc).

La factorisation critique #

L’idée centrale est de couper le motif en deux parties, \( x = u\,v \), à un endroit bien choisi appelé position critique. On appelle cette découpe une factorisation critique. Sa propriété est que, à cet endroit, la plus petite répétition locale du motif est aussi grande que la période du motif entier : c’est le point du motif où il est « le plus difficile » de se répéter.

Un théorème garantit qu’une telle position existe toujours, et qu’on peut la trouver ainsi : on calcule la position de départ du plus grand suffixe du motif dans l’ordre alphabétique usuel, puis celle du plus grand suffixe dans l’ordre alphabétique inversé, et on retient la plus grande des deux positions (c’est-à-dire le plus court des deux suffixes).

Pour le motif x = "aaab", les suffixes sont "aaab", "aab", "ab" et "b".

• Dans l’ordre usuel, le plus grand suffixe est "b", qui commence à la position 3.
• Dans l’ordre inversé (où b vient avant a), le plus grand suffixe est "aaab", qui commence à la position 0.

On retient donc la position critique \( \ell = 3 \), soit \( u = \texttt{"aaa"} \) et \( v = \texttt{"b"} \).

Ce calcul se fait en temps \( O(m) \) et en mémoire constante :

FONCTION suffixeMaximal(x, ordreInverse)
    m ← longueur(x)
    i ← -1          // début (moins 1) du meilleur suffixe trouvé
    j ← 0           // début du suffixe candidat
    k ← 1           // décalage de comparaison
    p ← 1           // période courante
    TANT QUE j + k < m
        a ← x[j + k]
        b ← x[i + k]
        SI ordreInverse ALORS échanger les rôles de a et b FIN SI
        SI a < b ALORS              // le candidat est plus petit : on l'abandonne
            j ← j + k
            k ← 1
            p ← j - i
        SINON SI a == b ALORS       // on progresse dans une répétition
            SI k == p ALORS
                j ← j + p
                k ← 1
            SINON
                k ← k + 1
            FIN SI
        SINON                       // le candidat est plus grand : il devient le meilleur
            i ← j
            j ← j + 1
            k ← 1
            p ← 1
        FIN SI
    FIN TANT QUE
    retourner (i + 1, p)            // position du suffixe maximal et période
FIN FONCTION

FONCTION factorisationCritique(x)
    (l1, p1) ← suffixeMaximal(x, FAUX)
    (l2, p2) ← suffixeMaximal(x, VRAI)
    SI l2 < l1 ALORS
        retourner (l1, p1)
    SINON
        retourner (l2, p2)
    FIN SI
FIN FONCTION

La recherche #

Une fois le motif coupé en \( u\,v \), on compare d’abord la partie droite \( v \) de gauche à droite, puis, seulement si elle correspond entièrement, la partie gauche \( u \) de droite à gauche. C’est cet ordre de comparaison (d’où le nom « deux sens ») qui permet de garantir que chaque caractère du texte n’est examiné qu’un nombre borné de fois.

FONCTION rechercheDeuxSens(t, x)
    n ← longueur(t)
    m ← longueur(x)
    (l, p) ← factorisationCritique(x)

    SI x[0 .. l-1] == x[p .. p+l-1] ALORS
        // Cas périodique : le motif se répète, on garde une « mémoire »
        decalage ← p
        memoire ← m - p
    SINON
        // Cas apériodique : on peut sauter loin
        decalage ← max(l, m - l) + 1
        memoire ← 0
    FIN SI

    pos ← 0
    dejaVu ← 0
    TANT QUE pos + m ≤ n
        // 1. On compare la partie droite v, de gauche à droite
        i ← max(l, dejaVu)
        TANT QUE i < m ET x[i] == t[pos + i]
            i ← i + 1
        FIN TANT QUE
        SI i < m ALORS
            pos ← pos + (i - l + 1)      // saut proportionnel à ce qui a été vérifié
            dejaVu ← 0
        SINON
            // 2. On compare la partie gauche u, de droite à gauche
            j ← l - 1
            TANT QUE j ≥ dejaVu ET x[j] == t[pos + j]
                j ← j - 1
            FIN TANT QUE
            SI j < dejaVu ALORS
                retourner pos            // motif trouvé
            FIN SI
            pos ← pos + decalage
            dejaVu ← memoire
        FIN SI
    FIN TANT QUE
    retourner -1
FIN FONCTION

Deux points méritent d’être soulignés. D’abord, lorsque la comparaison de la partie droite échoue à l’indice i, on décale le motif de i - l + 1 positions : plus on a vérifié de caractères avec succès, plus le saut est grand. C’est le contraire de l’algorithme naïf, qui avance toujours d’une seule position. Ensuite, dans le cas périodique, la variable dejaVu mémorise la longueur du préfixe déjà validé lors de l’alignement précédent, ce qui évite de recomparer les mêmes caractères. Cette mémoire tient dans un seul entier, d’où l’usage de mémoire en \( O(1) \).

Retour sur l’exemple qui dégénère #

Reprenons t = "aaaaaaaa" et x = "aaab". On a vu que la position critique est \( \ell = 3 \), avec u = "aaa" et v = "b". La période calculée est \( p = 1 \), mais x[0..2] = "aaa" diffère de x[1..3] = "aab" : on est donc dans le cas apériodique, avec un décalage de \( \max(3, 1) + 1 = 4 \).

L’algorithme compare alors, à chaque alignement, le caractère x[3] = 'b' avec t[pos + 3] = 'a' :

Cinq comparaisons au lieu de vingt. Et surtout, le comportement ne se dégrade pas quand le motif s’allonge : la partie gauche "aaa" n’est jamais examinée, puisque la partie droite échoue immédiatement. Pour un texte d’un million de a et un motif de mille caractères, l’algorithme two-way fait environ un million de comparaisons, contre un milliard pour l’algorithme naïf.

De façon générale, l’algorithme two-way effectue au plus \( 2n - m \) comparaisons de caractères durant la phase de recherche, quel que soit le texte et quel que soit le motif. Notons toutefois qu’il examine, lui aussi, presque tous les caractères du texte : contrairement à Boyer-Moore et à Horspool, il n’est pas sous-linéaire. C’est pourquoi les implémentations réelles (comme celle de la glibc) lui ajoutent une table de mauvais caractère pour accélérer le cas courant, tout en conservant la garantie du pire cas.

Comparaison des algorithmes #

Rappelons que \( n \) est la longueur du texte, \( m \) celle du motif et \( |\Sigma| \) la taille de l’alphabet.

Trois enseignements se dégagent de ce tableau. D’abord, aucun de ces algorithmes n’est meilleur que les autres sous tous les angles : Horspool a le pire des pires cas, mais c’est souvent le plus rapide en pratique ; two-way a la meilleure garantie, mais il ne saute jamais de caractères. Ensuite, un algorithme peut être sous-linéaire, c’est-à-dire lire moins de caractères qu’il n’y en a dans le texte : c’est possible parce qu’on n’a pas besoin de connaître tout le texte pour affirmer que le motif en est absent. Enfin, la complexité en mémoire compte autant que celle en temps : une table de taille \( |\Sigma| \) est un obstacle réel si l’alphabet est celui d’Unicode plutôt que celui de l’ASCII.

En pratique, la méthode indexOf de Java utilise un algorithme naïf, mais accéléré par des instructions spécialisées du processeur qui comparent plusieurs caractères à la fois. Pour des textes et des motifs ordinaires, c’est souvent le choix le plus rapide. Les algorithmes comme two-way deviennent intéressants lorsqu’on ne peut pas exclure les cas pathologiques, par exemple lorsque le motif est fourni par un utilisateur qui pourrait chercher à ralentir le système.

Tri #

Le tri consiste à réorganiser les éléments d’un tableau ou d’une liste selon un ordre donné (par exemple, croissant). Un algorithme de tri naïf, comme le tri à bulles (bubble sort) ou le tri par insertion, compare chaque élément à tous les autres et échange leur position si nécessaire. Ces algorithmes effectuent environ \( n^2 \) comparaisons pour un tableau de taille \( n \), ce qui leur donne une complexité en \( O(n^2) \). Cela devient très lent dès que le nombre d’éléments augmente.

Pseudocode du tri à bulle:

POUR i de 0 à n-2
    POUR j de 0 à n-2-i
        SI tableau[j] > tableau[j+1] ALORS
            échanger tableau[j] et tableau[j+1]
        FIN SI
    FIN POUR
FIN POUR

Le tri à bulle est un algorithme de tri simple qui parcourt un tableau de manière répétée pour comparer et échanger les éléments adjacents s’ils sont dans le mauvais ordre. Dans le pseudocode présenté, la boucle externe (i de 0 à n-2) contrôle le nombre de passes sur le tableau, chaque passe garantissant que l’élément le plus grand non encore trié est placé à la fin. La boucle interne (j de 0 à n-2-i) compare chaque paire d’éléments consécutifs (tableau[j] et tableau[j+1]) et les échange s’ils sont mal ordonnés (tableau[j] > tableau[j+1]). À chaque itération, les éléments les plus grands “remontent” comme des bulles vers la fin du tableau, d’où le nom de l’algorithme.

Utilisez cette application pour mieux comprendre le tri à bulle.

Un autre algorithme simple est le tri par insertion. Il parcourt le tableau élément par élément, insérant chaque nouvel élément à sa place dans la partie déjà triée.

POUR i de 1 à n-1
    clé ← tableau[i]
    j ← i - 1
    TANT QUE j ≥ 0 ET tableau[j] > clé
        tableau[j+1] ← tableau[j]
        j ← j - 1
    FIN TANT QUE
    tableau[j+1] ← clé
FIN POUR

Le tri par insertion est un algorithme de tri qui construit progressivement une partie triée du tableau en insérant chaque élément à sa position correcte. Dans le pseudocode fourni, la boucle externe (i de 1 à n-1) sélectionne chaque élément (clé ← tableau[i]) à partir du deuxième élément. La boucle interne compare cette clé avec les éléments de la partie déjà triée (de j ← i-1 jusqu’à 0), en déplaçant les éléments plus grands que la clé d’une position vers la droite (tableau[j+1] ← tableau[j]) tant que tableau[j] > clé et j ≥ 0. Une fois la bonne position trouvée, la clé est insérée (tableau[j+1] ← clé). Ce processus répété garantit que, à chaque étape, la sous-partie du tableau jusqu’à l’indice i est triée, aboutissant à un tableau entièrement trié à la fin.

Utilisez cette application pour mieux comprendre le tri par insertion.

Heureusement, il existe des algorithmes de tri plus efficaces. Par exemple, le tri fusion (merge sort) utilise une approche « diviser pour régner » : il divise le tableau en deux moitiés, trie chaque moitié récursivement, puis fusionne les deux moitiés triées en un seul tableau trié. Cette méthode réduit considérablement le nombre de comparaisons nécessaires et atteint une complexité en \( O(n \log n) \).

Idée générale du trie fusion :

1. Si le tableau contient 0 ou 1 élément, il est déjà trié.
2. Sinon, on divise le tableau en deux parties de taille à peu près égale.
3. On trie récursivement chaque partie.
4. On fusionne les deux parties triées pour obtenir un tableau final trié.

Pseudocode du tri fusion:

FONCTION triFusion(tableau)
    SI taille(tableau) ≤ 1 ALORS
        retourner tableau
    FIN SI
    milieu ← taille(tableau) // 2
    gauche ← triFusion(tableau[0 .. milieu-1])
    droite ← triFusion(tableau[milieu .. fin])
    retourner fusionner(gauche, droite)
FIN FONCTION

FONCTION fusionner(gauche, droite)
    résultat ← tableau vide
    TANT QUE gauche et droite ne sont pas vides
        SI gauche[0] ≤ droite[0] ALORS
            ajouter gauche[0] à résultat
            retirer gauche[0] de gauche
        SINON
            ajouter droite[0] à résultat
            retirer droite[0] de droite
        FIN SI
    FIN TANT QUE
    ajouter le reste de gauche (s’il en reste) à résultat
    ajouter le reste de droite (s’il en reste) à résultat
    retourner résultat
FIN FONCTION

Le pseudocode décrit deux fonctions principales. La fonction triFusion divise récursivement le tableau en deux moitiés jusqu’à ce que chaque sous-tableau ait au plus un élément (déjà trié). Pour cela, elle calcule l’indice milieu, trie récursivement la moitié gauche (0 à milieu-1) et la moitié droite (milieu à fin), puis fusionne ces deux sous-tableaux triés. La fonction fusionner combine les sous-tableaux gauche et droite en un tableau trié : elle compare les premiers éléments de chaque sous-tableau, ajoute le plus petit à résultat, et retire cet élément de son sous-tableau d’origine. Ce processus continue jusqu’à ce qu’un des sous-tableaux soit vide, puis les éléments restants de l’autre sous-tableau sont ajoutés à résultat.

Le tri fusion est donc beaucoup plus rapide que les tris naïfs pour les grands tableaux, et il illustre l’intérêt des algorithmes efficaces en informatique.

Utilisez cette application pour mieux comprendre le tri fusion.

Un autre algorithme performant est le tri rapide (quick sort). Il choisit un élément pivot, partitionne le tableau en deux sous-tableaux (les éléments plus petits que le pivot et ceux plus grands), puis trie récursivement chaque sous-tableau. En moyenne, sa complexité est en \( O(n \log n) \), bien qu’il puisse atteindre \( O(n^2) \) dans le pire cas (par exemple, si le tableau est déjà trié et que le pivot est mal choisi). Le choix du pivot est crucial : une stratégie courante est de sélectionner la médiane de trois valeurs ou un élément aléatoire.

FONCTION triRapide(tableau, début, fin)
    SI début < fin ALORS
        pivot ← partitionner(tableau, début, fin)
        triRapide(tableau, début, pivot - 1)
        triRapide(tableau, pivot + 1, fin)
    FIN SI
FIN FONCTION

FONCTION partitionner(tableau, début, fin)
    pivot ← tableau[fin]
    i ← début - 1
    POUR j de début à fin - 1
        SI tableau[j] ≤ pivot ALORS
            i ← i + 1
            échanger tableau[i] et tableau[j]
        FIN SI
    FIN POUR
    échanger tableau[i + 1] et tableau[fin]
    retourner i + 1
FIN FONCTION

La fonction triRapide vérifie si l’intervalle à trier (de début à fin) contient plus d’un élément ; si oui, elle appelle partitionner pour réorganiser le tableau autour d’un pivot, puis trie récursivement les sous-tableaux à gauche (de début à pivot-1) et à droite (de pivot+1 à fin). La fonction partitionner sélectionne le dernier élément comme pivot (tableau[fin]) et réarrange le tableau de sorte que les éléments inférieurs ou égaux au pivot soient à gauche et les plus grands à droite. Elle utilise un indice i pour suivre la frontière des éléments plus petits et échange les éléments appropriés via un parcours (j de début à fin-1). Enfin, le pivot est placé à sa position finale (échange avec tableau[i+1]), et son indice (i+1) est retourné.

Utilisez cette application pour mieux comprendre le tri rapide.

Le tri rapide est souvent le plus rapide en pratique pour plusieurs raisons. Premièrement, le tri rapide est efficace en termes de localité de mémoire. Il travaille directement sur le tableau (tri en place), ce qui minimise les accès mémoire et exploite bien la mémoire tampon des processeurs modernes. Comparé au tri fusion, qui nécessite un tableau auxiliaire pour la fusion, le tri rapide réduit les allocations de mémoire et les copies d’éléments. Deuxièmement, le tri rapide effectue moins de comparaisons en moyenne. Lors du partitionnement, il répartit les éléments autour d’un pivot, ce qui réduit rapidement la taille des sous-tableaux à trier. Si le pivot est bien choisi (par exemple, proche de la médiane), les sous-tableaux sont équilibrés, conduisant à une division efficace du problème. Même avec un choix de pivot aléatoire, les cas défavorables sont rares dans des données réelles. Troisièmement, le tri rapide est adaptable aux données. Dans des ensembles partiellement triés ou avec des motifs courants, il peut tirer parti de ces structures pour réduire le nombre d’échanges. Par exemple, un bon choix de pivot peut minimiser les réarrangements inutiles.

Utilisez l’application suivante pour comparer les techniques de tri. Appuyez sur Lancer tous les tris et regardez les 4 algorithmes s’exécuter en même temps. Constatez que certains algorithmes sont plus rapides que d’autres. Que pensez-vous qu’il se passerait si nous avions moins d’éléments (par ex., 4) ou beaucoup plus d’éléments (par ex., 1000) ?

Pour trier des objets, Java utilise généralement Timsort (par exemple via Arrays.sort sur des tableaux d’objets). Timsort est un algorithme de tri hybride, conçu par Tim Peters. Il combine le tri par insertion et le tri fusion pour optimiser les performances sur des données réelles, en exploitant les séquences déjà triées, appelées runs. L’algorithme commence par diviser le tableau en petits runs, soit naturels (séquences croissantes ou décroissantes), soit créés en triant des blocs de taille minimale (souvent 32 éléments) avec le tri par insertion. Ces runs sont ensuite fusionnés deux à deux à l’aide d’une version optimisée du tri fusion, qui minimise les comparaisons et les copies. Sa complexité est en \( O(n \log n) \) dans le pire cas, mais elle peut descendre à \( O(n) \) pour des données presque triées, rendant Timsort particulièrement efficace en pratique. De plus, Timsort est stable, préservant l’ordre relatif des éléments égaux, ce qui est crucial dans certaines applications.

Dans certains cas spécialisés, nous utilisons l’algorithme de tri par niches, également connu sous le nom de pigeonhole sort, un algorithme de tri non comparatif adapté aux ensembles de données où les éléments appartiennent à un ensemble fini de valeurs entières, comme des nombres dans une plage limitée. Il repose sur le principe des “niches” (ou pigeonholes) : chaque valeur possible est associée à une niche, et les éléments sont placés dans la niche correspondant à leur valeur. Ensuite, les niches sont parcourues dans l’ordre pour reconstruire le tableau trié. Sa complexité est en \( O(n + k) \), où \( n \) est le nombre d’éléments et \( k \) la taille de la plage de valeurs. Cet algorithme est très efficace lorsque \( k \) est proche de \( n \), mais il nécessite un espace auxiliaire proportionnel à \( k \) et n’est pas adapté aux données non entières ou à des plages de valeurs très grandes.

FONCTION triParNiches(tableau, min, max)
    k ← max - min + 1  // Taille de la plage de valeurs
    niches ← tableau de taille k, initialisé à vide

    // Étape 1 : placer les éléments dans les niches
    POUR chaque élément dans tableau
        index ← élément - min
        ajouter élément à niches[index]
    FIN POUR

    // Étape 2 : reconstruire le tableau trié
    index ← 0
    POUR i de 0 à k-1
        TANT QUE niches[i] n’est pas vide
            tableau[index] ← premier élément de niches[i]
            retirer premier élément de niches[i]
            index ← index + 1
        FIN TANT QUE
    FIN POUR

    retourner tableau
FIN FONCTION

Le tri par niches (ou bucket sort) est un algorithme de tri non comparatif adapté aux données uniformément réparties dans une plage de valeurs connue (de min à max). Le pseudocode décrit un processus en deux étapes. D’abord, il calcule la taille de la plage (k ← max - min + 1) et crée un tableau niches de taille k, où chaque niche correspond à une valeur possible. Dans l’étape 1, chaque élément du tableau est placé dans la niche correspondante (index ← élément - min), ce qui regroupe les éléments de même valeur. Dans l’étape 2, le tableau est reconstruit en parcourant les niches dans l’ordre (de 0 à k-1) et en extrayant leurs éléments pour les placer séquentiellement dans le tableau (tableau[index]). L’indice index suit la position d’insertion.

Exemple d’algorithme linearithmique #

Un algorithme est en \( O(n \log n) \) lorsque son temps d’exécution croît un peu plus vite qu’un algorithme linéaire, mais nettement moins vite qu’un algorithme quadratique. Cette complexité apparaît souvent dans les algorithmes qui divisent un problème en sous-problèmes de taille plus petite, puis combinent les résultats. Un exemple classique est le tri fusion. À chaque appel, le tableau est séparé en deux parties de taille à peu près égale. Si l’on part d’un tableau de taille \( n \), après une division on obtient des sous-tableaux de taille environ \( n/2 \), puis \( n/4 \), puis \( n/8 \), et ainsi de suite. Après \( k \) niveaux de division, la taille des sous-tableaux est donc d’environ \( n/2^k \). On s’arrête lorsque cette taille atteint 1, donc lorsque \( n/2^k = 1 \). Cela donne \( n = 2^k \), donc \( k = \log_2 n \). Voilà d’où vient le logarithme dans la complexité du tri fusion. Ensuite, à chaque niveau, l’étape de fusion parcourt l’ensemble des éléments à remettre en ordre, ce qui demande un travail linéaire en \( n \). On obtient donc intuitivement environ \( \log n \) niveaux de division, chacun demandant un travail total proportionnel à \( n \). C’est pourquoi le coût total est en \( O(n \log n) \).

Exemples de limite de l’analyse asymptotique #

La notation grand O est très utile pour comprendre le comportement d’un algorithme lorsque la taille de l’entrée devient très grande. Toutefois, elle ne suffit pas toujours pour déterminer quel algorithme sera le plus rapide dans une situation concrète. Voici quelques exemples.

Même grand O, vitesses différentes #

Supposons deux algorithmes linéaires. Le premier effectue environ \( n \) opérations, tandis que le second en effectue environ \( 100n \). Les deux sont en \( O(n) \), mais pour des tailles réalistes, le premier sera souvent beaucoup plus rapide.

Par exemple, un parcours simple d’un tableau et un autre parcours qui effectue de nombreux calculs compliqués sur chaque élément sont tous deux linéaires. La notation grand O les place dans la même classe, mais elle ne permet pas de conclure lequel sera le plus rapide en pratique.

Petite taille d’entrée #

Un algorithme en \( O(n^2) \) peut être plus rapide qu’un algorithme en \( O(n \log n) \) lorsque \( n \) est petit. C’est une raison pour laquelle des algorithmes comme le tri par insertion sont encore utilisés dans de vraies bibliothèques logicielles pour de petits tableaux.

Par exemple, pour trier 5 ou 10 éléments, un tri par insertion peut être plus rapide qu’un tri fusion, même si asymptotiquement le tri fusion est meilleur. Le coût des appels récursifs, des copies ou de la gestion de structures auxiliaires peut dominer lorsque l’entrée est petite.

Même grand O, mais cas moyens très différents #

Deux algorithmes peuvent partager la même notation \( O(n^2) \) dans le pire cas, tout en ayant des comportements très différents sur des données ordinaires. Par exemple, le tri à bulles et le tri par insertion sont souvent classés en \( O(n^2) \), mais le tri par insertion est souvent meilleur en pratique, surtout lorsque les données sont déjà presque triées.

La notation grand O, prise seule, ne dit pas si l’on parle du pire cas, du cas moyen ou du meilleur cas. Si l’on ne précise pas ce point, elle ne suffit pas pour prédire la vitesse observée.

Effets de mémoire et d’implantation #

La rapidité réelle dépend aussi de facteurs que la notation asymptotique ignore : mémoire cache, allocations, copies, accès disque, langage de programmation, compilateur, machine utilisée, etc.

Par exemple, le tri rapide et le tri fusion sont souvent décrits comme étant en \( O(n \log n) \). Pourtant, le tri rapide est souvent plus rapide en pratique parce qu’il travaille fréquemment directement dans le tableau et profite mieux de la mémoire cache. La notation grand O ne capture pas ce genre d’effet.

Vidéo suggérée #

Analyse amortie #

L’analyse amortie évalue le coût d’une opération non pas isolément, mais en la replaçant dans une suite d’opérations. Certaines structures de données ont en effet un comportement irrégulier : la grande majorité des opérations sont très rapides, mais quelques-unes, beaucoup plus rares, sont coûteuses. Ne regarder que le pire cas d’une opération isolée donne alors une image trompeusement pessimiste de la structure. L’analyse amortie considère plutôt le coût total d’une suite de \( n \) opérations, puis le divise par \( n \) : on obtient le coût moyen par opération sur l’ensemble de la séquence.

L’exemple classique est le tableau dynamique, comme la classe ArrayList en Java. Un tableau a une taille fixe : lorsqu’il est plein et qu’on veut y ajouter un élément de plus, il faut allouer un nouveau tableau plus grand et y recopier tout le contenu, ce qui coûte \( O(n) \). Prise isolément, cette insertion est donc coûteuse. Mais si on double la capacité à chaque agrandissement, les recopies se raréfient très vite : on recopie après 1 élément, puis 2, puis 4, puis 8, et ainsi de suite. Pour insérer \( n \) éléments, le total des recopies vaut donc \( 1 + 2 + 4 + \dots + n \), une somme qui reste inférieure à \( 2n \). Le coût total des \( n \) insertions est ainsi en \( O(n) \), soit un coût amorti de \( O(1) \) par insertion. Autrement dit, ajouter un élément à une ArrayList coûte en moyenne un temps constant, même si une insertion sur plusieurs milliers est nettement plus lente que les autres.

Il ne faut pas confondre coût amorti et coût moyen. Le coût moyen repose sur une hypothèse à propos des données : il décrit ce qui se produit « en général », mais rien n’empêche une entrée particulièrement défavorable d’être lente, et de l’être à répétition. Le coût amorti, lui, est une garantie sur la séquence complète : quelle que soit la suite d’opérations demandée, son coût total ne dépassera pas la borne annoncée. Une opération peut être lente, mais elle ne peut pas l’être souvent, car c’est justement le travail des opérations rapides qui rend la suivante coûteuse.

Cette distinction est utile pour lire correctement les garanties annoncées par les structures de données, à commencer par celle de la section suivante.

Table de hachage #

Une table de hachage (ou « hash table ») est une structure de données qui permet d’associer des clés à des valeurs et d’accéder très rapidement à une valeur à partir de sa clé. Le principe repose sur l’utilisation d’une fonction de hachage qui transforme la clé (par exemple, un texte ou un nombre) en un indice de tableau. Les opérations d’insertion, de recherche et de suppression se font en temps moyen \( O(1) \), c’est-à-dire en temps constant, quelle que soit la taille de la table (si la fonction de hachage est bonne et la table bien dimensionnée). La table de hachage est efficace pour retrouver rapidement une information à partir d’une clé.

Idée générale :

1. On applique une fonction de hachage à la clé pour obtenir un indice.
2. On stocke la valeur à cet indice dans un tableau.
3. En cas de « collision » (deux clés différentes qui donnent le même indice), on utilise une technique de résolution (chaînage, sondage linéaire, etc.).

Pseudocode d’une recherche dans une table de hachage (sans collision):

FONCTION rechercher(table, clé)
    indice ← hachage(clé)
    SI table[indice] == clé ALORS
        retourner VRAI
    SINON
        retourner FAUX
    FIN SI
FIN FONCTION

Le pseudocode décrit une fonction de recherche dans une table de hachage, une structure de données optimisée pour retrouver rapidement un élément. La fonction rechercher prend une table (tableau représentant la table de hachage) et une clé à chercher (clé). Elle commence par calculer l’indice correspondant à la clé via une fonction de hachage (indice ← hachage(clé)), qui mappe la clé à une position dans la table. Ensuite, elle vérifie si l’élément à cet indice (table[indice]) est égal à la clé recherchée. Si c’est le cas, la fonction retourne VRAI, indiquant que la clé est présente. Sinon, elle retourne FAUX, signifiant que la clé est absente. Ce pseudocode suppose une table de hachage simple sans gestion des collisions (cas où plusieurs clés pointent vers le même indice), ce qui la rend efficace mais limitée aux cas où chaque indice contient au plus un élément.

Pour mieux comprendre, testez l’application suivante. Saisissez des chaînes de caractères qui seront ajoutées à la table de hachage. Pouvez-vous créer une collision ?

En Java, la classe HashMap que nous verrons plus loin dans le cours implémente une table de hachage. Par exemple :

import java.util.HashMap;

HashMap<String, Integer> dico = new HashMap<>();
dico.put("chat", 1);
dico.put("chien", 2);
System.out.println(dico.get("chat")); // Affiche 1

Ce code Java utilise une HashMap pour créer une structure de données associant des clés à des valeurs. Une instance HashMap<String, Integer> est déclarée, avec des clés de type String et des valeurs de type Integer. Deux paires clé-valeur sont ajoutées via la méthode put : “chat” associé à 1 et “chien” à 2. La méthode get(“chat”) récupère la valeur liée à la clé “chat”, soit 1, qui est ensuite affichée avec System.out.println.

Les tables de hachage sont omniprésentes en informatique car elles rendent possible la recherche rapide dans de grands ensembles de données.

Imaginons que l’on souhaite stocker un ensemble de chaînes de caractères de différentes longueurs, par exemple « chat », « chien », « girafe », « lion ». Pour retrouver rapidement une chaîne, on peut utiliser une table de hachage où la fonction de hachage choisie est simplement la longueur de la chaîne. Ainsi, « chat » (4 lettres) sera stocké à l’indice 4, « chien » (5 lettres) à l’indice 5, « girafe » (6 lettres) à l’indice 6, et ainsi de suite. Pour rechercher une chaîne, il suffit de calculer sa longueur et d’aller directement à l’indice correspondant dans le tableau. Cette opération ne dépend pas du nombre total de chaînes stockées, ce qui explique pourquoi la recherche est dite « en temps constant » : on ne parcourt pas toute la table, on accède directement à la bonne case.

Cependant, ce choix de fonction de hachage est très simple et peut provoquer des « collisions » : deux chaînes de même longueur, comme « lion » et « chat », auraient le même indice. Dans ce cas, il faut une méthode pour gérer ces collisions, par exemple en stockant les deux chaînes dans une liste à cet indice. En pratique, les tables de hachage utilisent des fonctions de hachage beaucoup plus sophistiquées, capables de transformer n’importe quelle clé (texte, nombre, etc.) en un indice réparti de façon plus uniforme dans le tableau. L’objectif reste toujours de minimiser les collisions, car tant qu’il y en a peu, la recherche, l’insertion et la suppression restent très rapides et efficaces, même avec de très grands ensembles de données.

Vidéo suggérée #

Un problème résoluble en temps linéaire ou quadratique #

Prenons le problème suivant : « Trouver s’il existe deux éléments dans un tableau qui, additionnés, donnent une valeur cible. »

Solution naïve (\( O(n^2) \)) :

POUR i de 0 à n-1
    POUR j de i+1 à n-1
        SI tableau[i] + tableau[j] == cible
            retourner VRAI
        FIN SI
    FIN POUR
FIN POUR
retourner FAUX

La boucle externe (POUR i de 0 à n-1) parcourt chaque élément du tableau, tandis que la boucle interne (POUR j de i+1 à n-1) examine tous les éléments suivants (à partir de i+1) pour éviter de considérer le même élément deux fois ou des paires redondantes. À chaque itération, la condition SI tableau[i] + tableau[j] == cible teste si la somme des éléments aux indices i et j égale la valeur cible. Si une telle paire est trouvée, la fonction retourne VRAI, indiquant que la solution existe. Si aucune paire ne satisfait la condition après avoir exploré toutes les combinaisons, la fonction retourne FAUX.

Ici, on teste toutes les paires possibles, ce qui prend un temps quadratique.

Solution optimisée (\( O(n) \)) :

On peut résoudre ce problème en temps linéaire en utilisant une structure de données comme un ensemble (set) :

initialiser un ensemble vide
POUR chaque élément x du tableau
    SI (cible - x) est dans l’ensemble
        retourner VRAI
    AJOUTER x à l’ensemble
FIN POUR
retourner FAUX

Initialement, un ensemble vide est créé pour stocker les éléments rencontrés. La boucle (POUR chaque élément x du tableau) parcourt chaque élément x du tableau. Pour chaque x, l’algorithme vérifie si cible - x (la valeur nécessaire pour atteindre la somme cible) est déjà dans l’ensemble. Si c’est le cas, une paire d’éléments dont la somme vaut cible a été trouvée, et la fonction retourne VRAI. Sinon, l’élément x est ajouté à l’ensemble pour être utilisé dans les itérations suivantes. Si la boucle se termine sans trouver une telle paire, la fonction retourne FAUX.

Ici, chaque élément est traité une seule fois, et si la recherche dans l’ensemble se fait en temps constant (en moyenne) ou \( O(1) \), la solution est en \( O(n) \). Dans la solution optimisée, la vérification « (cible - x) est dans l’ensemble » est cruciale. Il n’est pas garanti que la recherche se fasse en temps \( O(1) \), mais c’est possible avec une table de hachage.

Le crible d’Ératosthène #

Voici un second exemple où le choix de l’approche change la classe de complexité. Le problème : dresser la liste de tous les nombres premiers inférieurs ou égaux à \( n \). Rappelons qu’un nombre premier est un entier supérieur à 1 qui n’est divisible que par 1 et par lui-même.

La méthode directe consiste à examiner chaque nombre l’un après l’autre et à vérifier s’il est premier en cherchant un diviseur.

POUR k de 2 à n
    estPremier ← VRAI
    d ← 2
    TANT QUE d × d <= k FAIRE
        SI k mod d = 0 ALORS
            estPremier ← FAUX
            sortir de la boucle
        FIN SI
        d ← d + 1
    FIN TANT QUE
    SI estPremier ALORS
        afficher k
    FIN SI
FIN POUR

L’arrêt à \( d \times d \le k \) mérite une explication. Si \( k \) admet un diviseur, il en admet forcément un qui ne dépasse pas \( \sqrt{k} \) : les diviseurs vont par paires dont le produit vaut \( k \), et dans une telle paire l’un des deux est toujours inférieur ou égal à la racine. Tester au-delà de \( \sqrt{k} \) est donc inutile. Cette seule observation fait passer le test d’un coût \( k \) à un coût \( \sqrt{k} \).

Malgré cette optimisation, l’ensemble reste coûteux : chaque nombre premier oblige à parcourir toute la boucle jusqu’à sa racine, ce qui donne un total de l’ordre de \( n\sqrt{n} \) opérations.

Ératosthène de Cyrène, un savant grec du troisième siècle avant notre ère, a proposé une méthode radicalement différente. Plutôt que de se demander pour chaque nombre s’il est premier, on part de la liste de tous les nombres et on élimine les non-premiers en bloc. Le point clé est qu’il est bien plus facile d’énumérer les multiples d’un nombre que de tester une divisibilité : les multiples de 7 s’obtiennent par additions successives, sans aucune division.

On dresse donc un tableau de booléens, tous marqués « premier » au départ. On prend le premier nombre encore marqué, 2 : il est premier, et on raye tous ses multiples. Le suivant encore marqué est 3 : il est premier, on raye ses multiples. Et ainsi de suite. Ce qui survit à la fin est exactement l’ensemble des nombres premiers.

estPremier ← tableau de n+1 booléens, tous à VRAI
estPremier[0] ← FAUX
estPremier[1] ← FAUX

i ← 2
TANT QUE i × i <= n FAIRE
    SI estPremier[i] ALORS
        j ← i × i
        TANT QUE j <= n FAIRE
            estPremier[j] ← FAUX
            j ← j + i
        FIN TANT QUE
    FIN SI
    i ← i + 1
FIN TANT QUE

POUR k de 2 à n
    SI estPremier[k] ALORS
        afficher k
    FIN SI
FIN POUR

Deux détails de ce pseudocode ne sont pas anodins.

Le rayage commence à \( i \times i \) et non à \( 2i \). Les multiples plus petits, comme \( 2i \), \( 3i \) ou \( 4i \), ont déjà été rayés par les nombres premiers précédents : quand on traite 5, les nombres 10, 15 et 20 ont été éliminés par 2 et par 3. Le premier multiple de 5 encore intact est bien 25.

La boucle externe s’arrête à \( i \times i \le n \), pour la même raison que dans la méthode directe. Une fois passé \( \sqrt{n} \), tout nombre composé restant aurait déjà été rayé par un de ses facteurs plus petits.

Déroulons le crible jusqu’à 30. La racine de 30 valant environ 5,48, la boucle externe s’arrête après 5.

Il reste 2, 3, 5, 7, 11, 13, 17, 19, 23 et 29, soit les dix nombres premiers inférieurs à 30.

Le crible ne fait aucune division : uniquement des additions et des écritures en mémoire. Son coût total est en \( O(n \log \log n) \), une expression qu’il n’est pas nécessaire de savoir démontrer, mais dont il faut retenir qu’elle est à peine plus grande que \( n \). La fonction \( \log \log n \) croît si lentement qu’elle ne vaut même pas 3 pour un million.

L’écart en pratique est net. Pour dresser la liste des 17 984 nombres premiers inférieurs à 200 000, les divisions successives demandent environ 26 fois plus de temps que le crible.

Le crible a toutefois un défaut, et il illustre un compromis fréquent en informatique : il échange du temps contre de la mémoire. Il faut conserver un tableau de \( n \) booléens du début à la fin, alors que la méthode directe n’a besoin que de quelques variables. Pour énumérer les premiers jusqu’à un milliard, ce tableau devient encombrant. Et si l’on ne veut tester qu’un seul grand nombre plutôt que dresser une liste complète, le crible est le mauvais outil : mieux vaut alors une division directe, ou un test de primalité spécialisé.

La programmation dynamique #

Nous avons vu dans la section sur les problèmes difficiles qu’un algorithme glouton fait à chaque étape le choix qui paraît le meilleur sur le moment, sans jamais revenir en arrière, et qu’il ne donne généralement pas la solution optimale. La programmation dynamique est la technique qui permet, dans bien des cas, d’obtenir l’optimum sans pour autant tout essayer.

Le nom est trompeur : il ne s’agit ni de dynamisme, ni de programmation au sens d’écrire du code. Richard Bellman, qui a forgé l’expression dans les années 1950, employait le mot « programmation » au sens de planification, comme dans « programme de production ». Il a raconté avoir aussi choisi ce nom parce qu’il sonnait suffisamment inoffensif pour ne pas attirer l’attention de son bailleur de fonds militaire.

Un exemple qui tourne mal #

La suite de Fibonacci se définit simplement : les deux premiers termes valent 0 et 1, et chaque terme suivant est la somme des deux précédents. La définition se traduit directement en un algorithme récursif.

FONCTION fib(n)
    SI n < 2 ALORS
        retourner n
    FIN SI
    retourner fib(n-1) + fib(n-2)
FIN FONCTION

Cet algorithme est correct, court et lisible. Il est aussi catastrophiquement lent. Pour calculer fib(5), il faut fib(4) et fib(3) ; mais fib(4) réclame à son tour fib(3) et fib(2). La valeur fib(3) est donc calculée deux fois, entièrement, sans que la seconde exécution profite de la première. Plus bas dans l’arbre des appels, la répétition devient massive : fib(2) est recalculé cinq fois pour fib(6), des dizaines de fois pour fib(10).

Le nombre total d’appels vaut exactement \( 2 F(n+1) - 1 \), où \( F \) désigne la suite elle-même. Comme Fibonacci croît de façon exponentielle, le coût de l’algorithme aussi.

Ajouter 5 à \( n \) multiplie le travail par environ 11. Calculer fib(90) par cette méthode réclamerait plus de neuf milliards de milliards d’appels : au rythme mesuré ci-dessus, environ trois siècles, alors que le résultat tient sans problème dans un long.

Se souvenir des résultats #

Le défaut n’est pas la récursivité : c’est de recalculer indéfiniment les mêmes valeurs. Le problème possède beaucoup de sous-problèmes, mais peu de sous-problèmes distincts. Il n’y en a que \( n+1 \), de fib(0) à fib(n).

La correction est donc immédiate : on garde un carnet des résultats déjà obtenus. Avant de calculer, on consulte le carnet ; après avoir calculé, on y inscrit la réponse. Cette technique s’appelle la mémoïsation.

memo ← tableau de n+1 cases, toutes vides

FONCTION fib(n)
    SI n < 2 ALORS
        retourner n
    FIN SI
    SI memo[n] n'est pas vide ALORS
        retourner memo[n]
    FIN SI
    memo[n] ← fib(n-1) + fib(n-2)
    retourner memo[n]
FIN FONCTION

Le changement porte sur trois lignes, mais la complexité passe de l’exponentielle à \( O(n) \) : chaque valeur n’est calculée qu’une seule fois, et toutes les autres demandes sont servies par le carnet. Le calcul de fib(90), hors d’atteinte quelques lignes plus haut, devient instantané.

On peut aussi renverser la perspective. Plutôt que de partir de \( n \) et de descendre récursivement, on part du bas et on remonte en remplissant le tableau dans l’ordre. Cette variante s’appelle la tabulation.

FONCTION fib(n)
    SI n < 2 ALORS
        retourner n
    FIN SI
    table ← tableau de n+1 cases
    table[0] ← 0
    table[1] ← 1
    POUR i de 2 à n
        table[i] ← table[i-1] + table[i-2]
    FIN POUR
    retourner table[n]
FIN FONCTION

Le résultat est identique et le coût aussi, mais il n’y a plus aucun appel récursif : une simple boucle suffit. C’est souvent la forme préférée, car elle évite le risque de saturer la pile d’appels. Dans ce cas précis, on peut même remarquer que seules les deux dernières cases servent, ce qui permet de ramener la mémoire utilisée à deux variables.

Quand la technique s’applique #

La programmation dynamique demande deux conditions.

D’abord, le problème doit se décomposer en sous-problèmes dont les solutions optimales se combinent en une solution optimale du tout. C’est la propriété de sous-structure optimale, celle-là même qui est mentionnée à propos des algorithmes gloutons.

Ensuite, et c’est ce qui distingue vraiment la technique, ces sous-problèmes doivent se recouper : le même sous-problème doit revenir plusieurs fois. Sans recoupement, la mémoïsation ne sert à rien. C’est justement le cas du tri fusion : lorsqu’il découpe le tableau en deux moitiés, celles-ci n’ont aucun élément commun et aucun sous-problème ne se répète. Le tri fusion relève de la stratégie « diviser pour régner », pas de la programmation dynamique. On peut résumer la différence ainsi : diviser pour régner découpe en morceaux indépendants, la programmation dynamique découpe en morceaux qui se chevauchent.

Il est utile de comparer les trois approches vues jusqu’ici sur le problème du sac à dos. Dans la version où l’on peut prendre des fractions d’objets, l’approche gloutonne consistant à trier par rapport valeur sur poids donne l’optimum. Mais si les objets sont indivisibles, il faut les prendre ou les laisser entiers, et la même approche gloutonne échoue : elle peut remplir le sac avec un objet au bon rapport et se retrouver incapable de loger la combinaison réellement optimale. Essayer toutes les combinaisons coûterait \( 2^n \). La programmation dynamique résout ce problème exactement, en construisant un tableau indexé par le nombre d’objets considérés et la capacité restante.

Beaucoup de problèmes classiques se traitent ainsi : la distance d’édition entre deux chaînes, c’est-à-dire le nombre minimal d’insertions, de suppressions et de substitutions pour passer de l’une à l’autre, le rendu de monnaie avec un nombre minimal de pièces, ou encore la plus longue sous-séquence commune, qui est au cœur des outils comparant deux versions d’un fichier.

Les arbres en informatique #

Les arbres sont des structures de données hiérarchiques non linéaires, composées de nœuds reliés par des arêtes. Un arbre possède une racine unique, à partir de laquelle descendent des sous-arbres. Chaque nœud peut avoir zéro ou plusieurs enfants, mais un seul parent (sauf la racine). À partir du sommet, nous progressons vers les feuilles qui où se terminent la progression. Les arbres permettent de représenter des relations hiérarchiques naturelles, comme des dossiers dans un système de fichiers, des expressions arithmétiques ou des structures organisationnelles.

Parmi les arbres les plus utilisés figure l’arbre binaire, où chaque nœud a au plus deux enfants (gauche et droit). L’arbre binaire de recherche (ABR) est une variante particulièrement utile : pour tout nœud, les valeurs dans le sous-arbre gauche sont inférieures à celle du nœud, et celles dans le sous-arbre droit sont supérieures. Cela permet des opérations de recherche, insertion et suppression efficaces dans un arbre équilibré.

fonction rechercher(racine, valeur_cible)
    courant ← racine
    tant que courant n'est pas null
        si valeur_cible = courant.valeur
            retourner courant
        fin si
        
        si valeur_cible < courant.valeur
            courant ← courant.gauche
        sinon
            courant ← courant.droit
        fin si
    fin tant que
    
    retourner null  // valeur non trouvée
fin fonction

Pour mieux comprendre le fonctionnement d’un arbre de recherche binaire, utilisez l’application suivante.

Nous souhaitons garder la distance entre le sommet et les feuilles aussi petite que possible. Cette distance détermine notre complexité de recherche. L’arbre rouge-noir (red-black tree) est une des arbres les plus populaires, utilisée notamment dans les implémentations de Map et Set en Java (TreeMap, TreeSet). Chaque nœud est coloré en rouge ou noir, et l’arbre respecte cinq propriétés strictes : la racine est noire, chaque feuille (nil) est noire, un nœud rouge a des enfants noirs, tout chemin d’un nœud à une feuille contient le même nombre de nœuds noirs, et aucun chemin ne contient deux rouges consécutifs. Ces règles assurent que l’arbre reste approximativement équilibré, avec une hauteur maximale d’environ \( 2 \log n \). Lors d’insertions ou suppressions, des violations de couleur peuvent survenir ; elles sont corrigées par des opérations locales qui maintiennent l’équilibre. Les arbres rouge-noir offrent des performances garanties. Les opérations de recherche, insertion et suppression s’exécutent en \( O(\log n) \) dans le pire cas, où \( n \) est le nombre de nœuds. Dans ce cours, il n’est pas nécessaire de concevoir des structures en arbres.

Vidéo suggérée #

Les graphes #

Un arbre impose qu’un nœud n’ait qu’un seul parent et qu’il n’existe aucun cycle. Si on abandonne ces contraintes, on obtient une structure beaucoup plus générale : le graphe. Un graphe est constitué d’un ensemble de sommets (ou nœuds) et d’un ensemble d’arêtes qui relient certaines paires de sommets. Un arbre n’est en fait qu’un cas particulier de graphe.

Les graphes servent à représenter à peu près toutes les relations entre objets : un réseau routier (les villes sont des sommets, les routes des arêtes), un réseau social (les personnes et leurs amitiés), le web (les pages et les hyperliens), les dépendances entre les tâches d’un projet, ou encore les appels entre les méthodes d’un programme.

On distingue plusieurs variantes :

• Un graphe est non orienté si les arêtes se parcourent dans les deux sens (une route à double sens), et orienté si chaque arête a un sens (un lien web pointe de A vers B sans que B pointe vers A).
• Un graphe est pondéré si chaque arête porte une valeur numérique : une distance, une durée, un coût, une capacité.
• Un graphe est connexe si on peut aller de n’importe quel sommet à n’importe quel autre.

Pour représenter un graphe de \( n \) sommets et \( m \) arêtes en mémoire, on utilise principalement deux approches. La matrice d’adjacence est un tableau à deux dimensions de taille \( n \times n \) où la case \( (i, j) \) contient le poids de l’arête entre \( i \) et \( j \) (ou une valeur spéciale s’il n’y a pas d’arête). Elle permet de vérifier en temps \( O(1) \) si deux sommets sont reliés, mais occupe toujours \( O(n^2) \) en mémoire, même si le graphe a très peu d’arêtes. Les listes d’adjacence associent plutôt à chaque sommet la liste de ses voisins : la mémoire utilisée est en \( O(n + m) \), ce qui est bien préférable pour les graphes creux, c’est-à-dire ceux où \( m \) est beaucoup plus petit que \( n^2 \). En Java, on représente souvent un graphe par un Map<String, List<Arete>>.

Les deux parcours fondamentaux d’un graphe sont le parcours en largeur (BFS), qui visite les sommets par distance croissante en nombre d’arêtes à l’aide d’une file, et le parcours en profondeur (DFS), qui s’enfonce aussi loin que possible avant de revenir sur ses pas, à l’aide d’une pile ou de la récursivité. Les deux s’exécutent en \( O(n + m) \). Le parcours en largeur trouve le plus court chemin lorsque toutes les arêtes ont le même coût. Dès que les arêtes ont des poids différents, il faut un algorithme plus subtil.

L’algorithme de Dijkstra #

Edsger Dijkstra a conçu en 1956 un algorithme qui calcule le plus court chemin entre un sommet de départ et tous les autres sommets d’un graphe pondéré, à condition que les poids soient positifs. Il l’a imaginé, dit-il, en une vingtaine de minutes à la terrasse d’un café d’Amsterdam, pour illustrer les capacités d’un nouvel ordinateur.

L’idée est la suivante. On maintient pour chaque sommet une distance provisoire depuis la source : c’est la longueur du meilleur chemin trouvé jusqu’ici. Au départ, cette distance vaut 0 pour la source et l’infini pour tous les autres. On répète ensuite le geste suivant : parmi les sommets qu’on n’a pas encore traités, on choisit celui dont la distance provisoire est la plus petite. Comme tous les poids sont positifs, aucun détour ne pourra jamais faire mieux : cette distance est donc définitive, et le sommet est marqué comme visité. On en profite alors pour examiner ses voisins et, pour chacun, vérifier si passer par le sommet qu’on vient de fixer améliore la distance connue. C’est l’étape de relâchement (relaxation).

fonction dijkstra(graphe, source)
    pour chaque sommet v du graphe
        distance[v] ← ∞
        precedent[v] ← indéfini
        visite[v] ← faux
    fin pour

    distance[source] ← 0

    tant qu'il existe un sommet non visité dont la distance est finie
        u ← le sommet non visité ayant la plus petite distance
        visite[u] ← vrai

        pour chaque voisin v de u
            si visite[v] est faux
                candidat ← distance[u] + poids(u, v)
                si candidat < distance[v]
                    distance[v] ← candidat
                    precedent[v] ← u
                fin si
            fin si
        fin pour
    fin tant que

    retourner distance, precedent
fin fonction

L’algorithme ne construit pas le chemin directement : il retient seulement, dans le tableau precedent, par quel sommet on est arrivé à chaque destination. Pour obtenir le trajet complet, on remonte ce tableau à partir de la cible, puis on inverse le résultat.

fonction chemin(precedent, source, cible)
    resultat ← liste vide
    u ← cible
    tant que u est défini
        insérer u au début de resultat
        u ← precedent[u]
    fin tant que

    si resultat est vide ou son premier élément ≠ source
        retourner « aucun chemin »
    fin si

    retourner resultat
fin fonction

La complexité dépend de la façon dont on cherche le sommet non visité de distance minimale. Si on parcourt bêtement tous les sommets à chaque tour, on obtient \( O(n^2) \), ce qui reste raisonnable pour un graphe dense. Si on utilise plutôt une file de priorité (un tas, ou en Java une PriorityQueue), on descend à \( O((n + m) \log n) \), ce qui est nettement meilleur pour les graphes creux.

L’algorithme de Dijkstra exige des poids positifs ou nuls. Avec une arête de poids négatif, l’argument « le plus proche sommet non visité a sa distance définitive » s’effondre, car un détour pourrait encore réduire la distance. Il faut alors recourir à l’algorithme de Bellman-Ford, plus lent, en \( O(n \times m) \).

Dijkstra est au cœur des logiciels de navigation routière et du calcul des routes sur Internet. En pratique, les systèmes de cartographie utilisent des variantes accélérées, comme l’algorithme A*, qui ajoute une estimation de la distance restante jusqu’à la destination afin d’explorer en priorité les sommets qui vont dans la bonne direction.

Application interactive #

La carte ci-dessous représente le pays imaginaire de Sylvanie. Les cercles sont des villes et les traits des routes, avec leur longueur en kilomètres. Choisissez une ville de départ et une ville d’arrivée, puis lancez la recherche pour voir l’algorithme progresser pas à pas.

Le nombre affiché dans chaque cercle est la distance provisoire depuis la ville de départ. Une ville orange est celle que l’algorithme vient de choisir (sa distance devient définitive), une ville bleue est déjà visitée, une ville jaune a une distance provisoire mais n’est pas encore fixée, et une ville blanche est encore à l’infini. Le chemin final apparaît en rouge.

Observez que l’algorithme ne se contente pas de foncer vers la destination : il explore les villes dans l’ordre de leur distance au point de départ, un peu comme une tache d’huile qui s’étend. Il peut donc visiter des villes situées à l’opposé de la cible avant de conclure. C’est le prix à payer pour la garantie d’optimalité, et c’est précisément ce que corrige l’algorithme A* en orientant la recherche.

L’algorithme du lièvre et de la tortue #

Terminons par un graphe d’une forme particulière : celui où chaque sommet possède exactement un successeur. C’est le cas d’une liste chaînée, où chaque maillon pointe vers le suivant, ou d’une suite définie par récurrence, où chaque valeur détermine la suivante.

Dans un tel graphe, partons d’un sommet et suivons les flèches. Comme le nombre de sommets est fini et que chaque sommet mène toujours au même successeur, nous devons tôt ou tard revenir sur un sommet déjà visité, et à partir de là tourner en rond indéfiniment. Le trajet a donc la forme de la lettre grecque rho : une queue, parcourue une seule fois, puis un cycle parcouru sans fin.

Deux questions se posent. Y a-t-il un cycle, et si oui, où commence-t-il et quelle est sa longueur ? Détecter un cycle est utile en pratique : une liste chaînée dont un maillon pointe vers un maillon antérieur fera boucler indéfiniment tout programme qui la parcourt, et c’est une source classique de blocage.

La solution évidente consiste à mémoriser tous les sommets déjà visités dans un ensemble, et à s’arrêter dès qu’on en rencontre un pour la deuxième fois. C’est correct et rapide, mais cela demande une mémoire proportionnelle à la longueur du trajet. Sur une liste de plusieurs millions de maillons, cela peut être rédhibitoire.

Robert Floyd a proposé une méthode qui ne demande que deux variables, quelle que soit la taille du graphe. On lance deux marcheurs depuis le point de départ : la tortue avance d’un sommet à la fois, le lièvre de deux. Si le trajet se termine, le lièvre atteindra la fin le premier et il n’y a pas de cycle. Sinon, les deux finissent par se retrouver sur le même sommet.

Pourquoi cette rencontre est-elle certaine ? Une fois que les deux marcheurs sont entrés dans le cycle, le lièvre gagne exactement une position sur la tortue à chaque tour. L’écart entre eux, mesuré le long du cycle, diminue donc de 1 à chaque étape, jusqu’à devenir nul. Le lièvre ne peut pas « sauter par-dessus » la tortue, précisément parce qu’il ne la rattrape que d’un cran à la fois.

Reste à situer l’entrée du cycle. Il se trouve qu’au point de rencontre, la distance qui reste à parcourir pour atteindre l’entrée du cycle est égale à la distance entre le point de départ et cette même entrée, à un nombre entier de tours près. Il suffit donc de ramener un des deux marcheurs au point de départ et de les faire avancer tous les deux d’un pas à la fois : ils se rejoindront exactement à l’entrée du cycle. La longueur du cycle s’obtient ensuite en faisant un tour complet avec un seul marcheur.

FONCTION detecterCycle(depart)
    // Phase 1 : la rencontre
    tortue ← successeur(depart)
    lievre ← successeur(successeur(depart))
    TANT QUE tortue ≠ lievre FAIRE
        tortue ← successeur(tortue)
        lievre ← successeur(successeur(lievre))
    FIN TANT QUE

    // Phase 2 : l'entrée du cycle
    debut ← 0
    tortue ← depart
    TANT QUE tortue ≠ lievre FAIRE
        tortue ← successeur(tortue)
        lievre ← successeur(lievre)
        debut ← debut + 1
    FIN TANT QUE

    // Phase 3 : la longueur du cycle
    longueur ← 1
    lievre ← successeur(tortue)
    TANT QUE tortue ≠ lievre FAIRE
        lievre ← successeur(lievre)
        longueur ← longueur + 1
    FIN TANT QUE

    retourner debut, longueur
FIN FONCTION

Prenons un exemple concret. Sept sommets numérotés de 0 à 6, dont les successeurs sont donnés par le tableau successeur = [1, 2, 3, 4, 5, 6, 3]. En partant de 0, le trajet est

0 → 1 → 2 → 3 → 4 → 5 → 6 → 3 → 4 → 5 → 6 → 3 → ...

La queue est 0, 1, 2 et le cycle est 3, 4, 5, 6. Voici la première phase, tour par tour :

Ils se rencontrent au sommet 4. La deuxième phase repart de 0 avec la tortue, laisse le lièvre en 4, et les fait avancer d’un pas chacun : 1 et 5, puis 2 et 6, puis 3 et 3. Ils se rejoignent au sommet 3, qui est bien l’entrée du cycle, après 3 pas. La troisième phase fait un tour complet depuis 3 et compte 4 sommets.

L’algorithme parcourt un nombre d’étapes proportionnel à la longueur de la queue plus celle du cycle, donc \( O(n) \) au pire, mais il n’utilise qu’un nombre constant de variables, soit \( O(1) \) en mémoire. C’est exactement le genre de compromis que l’analyse de complexité permet de reconnaître : la solution par ensemble est aussi rapide, mais elle paie en mémoire ce que celle-ci obtient par une idée.

Vidéo optionnelle #