Les algorithmes à connaître

Tu utilises déjà des algorithmes tous les jours : chaque foreach, chaque sort(), chaque requête SQL en exécute un. Un algorithme, c'est simplement une suite d'étapes précises qui résout un problème.

Le but de cette fiche n'est pas de les réciter. Un développeur expérimenté ne connaît pas tout par cœur : il reconnaît la forme d'un problème (« je cherche le chemin le plus court », « je dois essayer des combinaisons ») et sait quel outil y répond. C'est une compétence qui s'apprend, comme le reste.

Les sections suivent un ordre de priorité : les trois premières te serviront chaque semaine, les dernières quelques fois par an. Si tu dois t'arrêter en route, arrête-toi après la section 3, tu auras déjà l'essentiel.

1.La complexité : compter le travail, pas les secondes

Commençons par un problème réel : retirer d'une newsletter les personnes qui se sont désinscrites. Voici deux versions qui donnent le même résultat.

<?php

declare(strict_types=1);

// 20 000 inscrits, 10 000 désinscrits : qui faut-il retirer de la newsletter ?
$subscribers = [];
$unsubscribed = [];
for ($i = 0; $i < 20_000; $i++) {
    $subscribers[] = "user$i@example.com";
    if ($i % 2 === 0) {
        $unsubscribed[] = "user$i@example.com";
    }
}

// Version 1 : in_array relit toute la liste à chaque tour → O(n²)
$start = hrtime(true);
$toRemove = [];
foreach ($subscribers as $email) {
    if (in_array($email, $unsubscribed, true)) {
        $toRemove[] = $email;
    }
}
printf("in_array : %d trouvés en %.1f ms\n", count($toRemove), (hrtime(true) - $start) / 1e6);

// Version 2 : on construit un index une seule fois, puis isset est en O(1) → O(n)
$start = hrtime(true);
$index = array_flip($unsubscribed);
$toRemove = [];
foreach ($subscribers as $email) {
    if (isset($index[$email])) {
        $toRemove[] = $email;
    }
}
printf("isset    : %d trouvés en %.1f ms\n", count($toRemove), (hrtime(true) - $start) / 1e6);

in_array : 10000 trouvés en 440.2 ms
isset    : 10000 trouvés en 0.6 ms

Même résultat, mais la première version est des centaines de fois plus lente. Pourquoi ? in_array parcourt toute la liste des désinscrits à chaque tour de la boucle : c'est une boucle cachée dans une boucle. Avec 20 000 inscrits, cela fait jusqu'à 200 millions de comparaisons.

La complexité décrit comment le travail grandit quand la quantité de données grandit. On l'écrit avec la notation O (« grand O ») : O(n) se lit « de l'ordre de n », où n est le nombre d'éléments. On regarde le pire cas et on ignore les détails : seul l'ordre de grandeur compte.

À 1 000 milliards d'opérations, un script PHP tourne pendant des heures. C'est pour ça qu'un code qui marche très bien en développement, avec 50 lignes en base, peut s'effondrer en production avec 100 000 lignes.

La règle pratique

1. Repère les boucles imbriquées sur les mêmes données : c'est souvent du O(n²).
2. Repère les boucles cachées : in_array, array_search, array_diff appelés dans une boucle, ou une requête SQL dans une boucle (le problème « N+1 », fiche 8).
3. Demande-toi combien de données il y aura en production dans deux ans, pas aujourd'hui.

2.Chercher : boucle ou tableau associatif

Tu as vu les deux façons de chercher dans l'exemple précédent.

1. La recherche linéaire parcourt les éléments un par un jusqu'à trouver : foreach, in_array, array_search, ou array_find (nouveau en PHP 8.4). C'est du O(n).
2. Le tableau associatif range chaque valeur sous une clé. En interne, PHP utilise une table de hachage : il calcule directement l'emplacement de la clé à partir de la clé elle-même, sans parcourir les autres. Lire $index[$key] ou tester isset($index[$key]) coûte donc O(1), quelle que soit la taille du tableau.

La technique à retenir : construire un index une seule fois, puis faire toutes les recherches dedans.

• array_flip($emails) transforme une liste de valeurs en clés.
• array_column($users, null, 'id') range des lignes par leur id : $usersById[42] donne directement l'utilisateur 42.

3.Trier

N'écris jamais ton propre algorithme de tri en production. Les fonctions de PHP sont en O(n log n), testées depuis des années, et stables depuis PHP 8.0 : deux éléments égaux gardent leur ordre d'origine. Ton travail se limite à dire comment comparer deux éléments.

<?php

declare(strict_types=1);

$products = [
    ['name' => 'Clavier', 'price' => 4990],   // prix en centimes
    ['name' => 'Souris', 'price' => 1990],
    ['name' => 'Moniteur', 'price' => 19900],
    ['name' => 'Tapis', 'price' => 1990],
];

// Par prix croissant, puis par nom si deux prix sont égaux.
// <=> compare les deux tableaux case par case et renvoie -1, 0 ou 1.
usort(
    $products,
    fn (array $a, array $b): int => [$a['price'], $a['name']] <=> [$b['price'], $b['name']],
);

foreach ($products as $product) {
    printf("%-9s %7.2f €\n", $product['name'], $product['price'] / 100);
}

Souris      19.90 €
Tapis       19.90 €
Clavier     49.90 €
Moniteur   199.00 €

La fonction de comparaison reçoit deux éléments et renvoie un nombre négatif si $a doit passer avant, positif s'il doit passer après, zéro s'ils sont égaux. L'opérateur <=> (« vaisseau spatial ») calcule exactement ça. Pour trier par ordre décroissant, inverse $a et $b.

• sort / rsort : trie les valeurs et renumérote les clés.
• asort / arsort : trie les valeurs en gardant les clés.
• ksort : trie par clé.
• usort / uasort : trie avec ta propre fonction de comparaison.

4.La recherche dichotomique

Tu connais le jeu « plus ou moins » : on cherche un nombre entre 1 et 1 000. La meilleure stratégie est de proposer 500, puis 250 ou 750, et ainsi de suite. Chaque réponse élimine la moitié des possibilités. En 10 essais, tu trouves n'importe quel nombre. Entre 1 et 1 million, il en faut seulement 20.

C'est la recherche dichotomique (en anglais binary search), en O(log n). Elle a une condition : les données doivent être triées. Ici, on cherche la tranche de frais de port qui correspond à un poids.

<?php

declare(strict_types=1);

/**
 * Renvoie l'indice du plus grand seuil inférieur ou égal à $value, ou -1.
 * $thresholds DOIT être trié par ordre croissant.
 *
 * @param list<int> $thresholds
 */
function findTier(array $thresholds, int $value): int
{
    $low = 0;
    $high = count($thresholds) - 1;
    $found = -1;

    while ($low <= $high) {
        $middle = intdiv($low + $high, 2);
        if ($thresholds[$middle] <= $value) {
            $found = $middle;      // candidat possible : on cherche plus grand à droite
            $low = $middle + 1;
        } else {
            $high = $middle - 1;   // trop grand : on cherche à gauche
        }
    }

    return $found;
}

$thresholds = [0, 500, 1000, 2000, 5000];   // poids en grammes
$fees = [450, 600, 850, 1200, 2000];        // frais de port en centimes

foreach ([250, 500, 1999, 7000] as $weight) {
    $tier = findTier($thresholds, $weight);
    printf("%5d g → %5.2f €\n", $weight, $fees[$tier] / 100);
}

  250 g →  4.50 €
  500 g →  6.00 €
 1999 g →  8.50 €
 7000 g → 20.00 €

Tu t'en sers déjà sans le savoir : un index de base de données (un « B-tree ») applique la même idée, et git bisect (fiche 4) trouve le commit qui a introduit un bug en coupant l'historique en deux à chaque étape.

5.La récursivité

Une fonction récursive est une fonction qui s'appelle elle-même sur un morceau plus petit du problème. Elle a toujours deux parties :

1. Le cas de base : le cas assez simple pour répondre sans s'appeler. Sans lui, la fonction ne s'arrête jamais.
2. L'appel récursif : la fonction s'appelle sur un problème plus petit, qui se rapproche du cas de base.

Elle est naturelle pour les données en arbre : chaque élément a des enfants, qui ont eux-mêmes des enfants, sans profondeur fixée à l'avance. Par exemple des catégories :

<?php

declare(strict_types=1);

// Les lignes telles qu'elles sortent d'une table SQL avec une colonne parent_id
$categories = [
    ['id' => 1, 'parent' => null, 'name' => 'Informatique'],
    ['id' => 2, 'parent' => 1, 'name' => 'Ordinateurs'],
    ['id' => 3, 'parent' => 2, 'name' => 'Portables'],
    ['id' => 4, 'parent' => 1, 'name' => 'Accessoires'],
    ['id' => 5, 'parent' => null, 'name' => 'Maison'],
];

// Index « parent → enfants » : encore un tableau associatif
$children = [];
foreach ($categories as $category) {
    $children[$category['parent'] ?? 0][] = $category;
}

function render(array $children, int $parentId, int $depth = 0): void
{
    // Cas de base : une catégorie sans enfant → la boucle ne tourne pas, on s'arrête
    foreach ($children[$parentId] ?? [] as $category) {
        echo str_repeat('  ', $depth), '- ', $category['name'], "\n";
        render($children, $category['id'], $depth + 1);   // l'appel récursif
    }
}

render($children, 0);

- Informatique
  - Ordinateurs
    - Portables
  - Accessoires
- Maison

Remarque que l'index $children est un tableau associatif (section 2) : sans lui, il faudrait reparcourir toutes les catégories à chaque appel.

6.Parcourir un graphe : en largeur ou en profondeur

Un graphe, c'est un ensemble d'éléments (les nœuds) reliés entre eux (par des arêtes). Les pages d'un site et leurs liens, des utilisateurs qui se suivent, les paquets Composer et leurs dépendances, des stations de métro : ce sont des graphes. Un arbre est un graphe particulier, sans boucle.

Il existe deux grandes façons de parcourir un graphe.

1. En largeur (BFS, breadth-first search) : on visite d'abord tous les voisins directs, puis les voisins des voisins, niveau par niveau. On range les nœuds à visiter dans une file d'attente (le premier arrivé est le premier servi). Comme on avance niveau par niveau, le premier chemin trouvé est le plus court en nombre d'étapes.
2. En profondeur (DFS, depth-first search) : on suit un chemin le plus loin possible, puis on revient en arrière pour essayer le suivant. On utilise une pile (le dernier arrivé est le premier servi) ou la récursivité. Utile pour tout explorer, détecter une boucle, ou trouver dans quel ordre installer des dépendances.

Exemple : combien de clics faut-il au minimum pour aller de l'accueil au panier ?

<?php

declare(strict_types=1);

// Chaque page et les pages vers lesquelles elle a un lien
$links = [
    '/' => ['/blog', '/produits'],
    '/blog' => ['/blog/php', '/contact'],
    '/blog/php' => ['/produits/clavier'],
    '/produits' => ['/produits/clavier'],
    '/produits/clavier' => ['/panier'],
    '/contact' => [],
    '/panier' => [],
];

/**
 * Parcours en largeur : renvoie le chemin le plus court en nombre de clics.
 *
 * @return list<string>|null
 */
function shortestPath(array $links, string $from, string $to): ?array
{
    $queue = new SplQueue();          // file d'attente : premier entré, premier sorti
    $queue->enqueue([$from]);
    $visited = [$from => true];       // pour ne jamais traiter deux fois la même page

    while (!$queue->isEmpty()) {
        $path = $queue->dequeue();
        $page = $path[array_key_last($path)];
        if ($page === $to) {
            return $path;
        }
        foreach ($links[$page] ?? [] as $next) {
            if (!isset($visited[$next])) {
                $visited[$next] = true;
                $queue->enqueue([...$path, $next]);
            }
        }
    }

    return null;                      // la page n'est pas atteignable
}

echo implode(' → ', shortestPath($links, '/', '/panier') ?? ['aucun chemin']), "\n";
echo implode(' → ', shortestPath($links, '/contact', '/') ?? ['aucun chemin']), "\n";

/ → /produits → /produits/clavier → /panier
aucun chemin

Le tableau $visited est indispensable. Dès qu'un graphe contient une boucle (la page A a un lien vers B, qui a un lien vers A), un parcours sans mémoire tourne à l'infini. Pour passer en profondeur, remplace SplQueue par SplStack, avec push() et pop() : le parcours trouvera un chemin, mais plus forcément le plus court.

7.Le backtracking (retour sur trace)

Imagine un labyrinthe. Tu avances. À un carrefour, tu choisis un couloir. S'il mène à une impasse, tu reviens au dernier carrefour et tu essaies le couloir suivant. C'est le backtracking : construire une solution pas à pas, et revenir en arrière dès qu'un choix ne mène nulle part. Il se résume en trois gestes :

1. Choisir une option.
2. Explorer la suite avec ce choix (par un appel récursif).
3. Annuler le choix si l'exploration échoue, puis essayer l'option suivante.

Exemple : quels articles prendre pour dépenser exactement une carte cadeau de 50 € ?

<?php

declare(strict_types=1);

/**
 * Cherche des articles dont le total fait exactement $target (en centimes).
 *
 * @param list<int> $prices
 * @param list<int> $chosen indices déjà choisis
 * @return list<int>|null
 */
function findExact(array $prices, int $target, int $start = 0, array $chosen = []): ?array
{
    if ($target === 0) {
        return $chosen;                   // solution trouvée
    }
    for ($i = $start; $i < count($prices); $i++) {
        if ($prices[$i] > $target) {
            continue;                     // élagage : trop cher, inutile d'explorer
        }
        $chosen[] = $i;                                                   // 1. choisir
        $result = findExact($prices, $target - $prices[$i], $i + 1, $chosen); // 2. explorer
        if ($result !== null) {
            return $result;
        }
        array_pop($chosen);                                               // 3. annuler
    }

    return null;                          // impasse : on revient en arrière
}

$names = ['Livre', 'Jeu', 'Mug', 'Casque', 'Stylo', 'Agenda'];
$prices = [1990, 2490, 1250, 3500, 990, 1520];

$solution = findExact($prices, 5000);     // une carte cadeau de 50 €
foreach ($solution ?? [] as $i) {
    printf("%-6s %5.2f €\n", $names[$i], $prices[$i] / 100);
}
echo $solution === null ? "Aucune combinaison\n" : '';

Jeu    24.90 €
Stylo   9.90 €
Agenda 15.20 €

Le test $prices[$i] > $target est un élagage : on coupe une branche dès qu'on sait qu'elle ne peut pas aboutir, sans l'explorer. C'est ce qui rend le backtracking utilisable en pratique. Note aussi que les prix sont en centimes : avec des nombres à virgule (float), 0.1 + 0.2 ne vaut pas exactement 0.3, et un total « exact » ne tomberait jamais juste.

<?php

declare(strict_types=1);

// (a+)+ : un groupe répété dans un groupe répété. Sur un texte qui ÉCHOUE,
// le moteur essaie toutes les façons de découper les « a » : 2^n essais.
$input = str_repeat('a', 30) . '!';

$start = hrtime(true);
$result = preg_match('/^(a+)+$/', $input);
printf(
    "résultat : %s, erreur : %s, durée : %d ms\n",
    var_export($result, true),
    preg_last_error_msg(),
    (hrtime(true) - $start) / 1e6,
);

résultat : false, erreur : Backtrack limit exhausted, durée : 1 ms

8.Mémoïsation et programmation dynamique

Dans la suite de Fibonacci, chaque nombre est la somme des deux précédents. La version récursive naïve recalcule sans cesse les mêmes valeurs : fibonacci(25) calcule fibonacci(23) deux fois, fibonacci(22) trois fois, et ainsi de suite.

<?php

declare(strict_types=1);

// Suite de Fibonacci : chaque nombre est la somme des deux précédents.
// $calls compte les appels, pour voir le travail réellement fait.
function fibonacci(int $n, int &$calls): int
{
    $calls++;

    return $n < 2 ? $n : fibonacci($n - 1, $calls) + fibonacci($n - 2, $calls);
}

function fibonacciMemo(int $n, int &$calls, array &$cache = []): int
{
    $calls++;
    if (isset($cache[$n])) {
        return $cache[$n];                // déjà calculé : on relit le résultat
    }

    return $cache[$n] = $n < 2
        ? $n
        : fibonacciMemo($n - 1, $calls, $cache) + fibonacciMemo($n - 2, $calls, $cache);
}

$calls = 0;
printf("sans cache : %d en %d appels\n", fibonacci(25, $calls), $calls);
$calls = 0;
printf("avec cache : %d en %d appels\n", fibonacciMemo(25, $calls), $calls);

sans cache : 75025 en 242785 appels
avec cache : 75025 en 49 appels

1. La mémoïsation consiste à garder en mémoire le résultat d'un appel pour ne jamais le recalculer. C'est un cache à l'échelle d'une fonction. Le composant Cache de Symfony applique la même idée à l'échelle d'une application (fiche 13).
2. La programmation dynamique va plus loin : elle résout d'abord les petits sous-problèmes, range leurs solutions dans un tableau, et construit la solution du grand problème à partir d'eux. La fonction optimalChange de la section suivante en est un exemple. La fonction levenshtein() de PHP, qui compte les modifications pour passer d'un mot à un autre, en est un autre.

9.Les algorithmes gloutons

Un algorithme glouton fait, à chaque étape, le choix qui paraît le meilleur tout de suite, sans jamais revenir en arrière. Il est simple et rapide. Exemple : rendre la monnaie en prenant toujours la plus grosse pièce possible.

<?php

declare(strict_types=1);

/**
 * Glouton : prend toujours la plus grosse pièce possible.
 *
 * @param list<int> $coins
 * @return list<int>
 */
function greedyChange(array $coins, int $amount): array
{
    rsort($coins);
    $result = [];
    foreach ($coins as $coin) {
        while ($amount >= $coin) {
            $amount -= $coin;
            $result[] = $coin;
        }
    }

    return $result;
}

/**
 * Programmation dynamique : calcule la meilleure solution pour 1, 2, 3… jusqu'à $amount,
 * en réutilisant les solutions déjà calculées pour les montants plus petits.
 *
 * @param list<int> $coins
 * @return list<int>|null
 */
function optimalChange(array $coins, int $amount): ?array
{
    $best = [0 => []];                    // $best[$x] = moins de pièces pour faire $x
    for ($x = 1; $x <= $amount; $x++) {
        $best[$x] = null;                 // null = impossible pour l'instant
        foreach ($coins as $coin) {
            if ($coin > $x || $best[$x - $coin] === null) {
                continue;
            }
            $candidate = [...$best[$x - $coin], $coin];
            if ($best[$x] === null || count($candidate) < count($best[$x])) {
                $best[$x] = $candidate;
            }
        }
    }

    return $best[$amount];
}

$euros = [1, 2, 5, 10, 20, 50, 100, 200];   // les pièces en centimes
echo 'Euros, 3,87 € glouton : ', implode(' + ', greedyChange($euros, 387)), "\n";

$odd = [1, 3, 4];                           // un système de pièces inventé
echo 'Pièces 1/3/4, glouton : ', implode(' + ', greedyChange($odd, 6)), "\n";
echo 'Pièces 1/3/4, optimal : ', implode(' + ', optimalChange($odd, 6) ?? []), "\n";

Euros, 3,87 € glouton : 200 + 100 + 50 + 20 + 10 + 5 + 2
Pièces 1/3/4, glouton : 4 + 1 + 1
Pièces 1/3/4, optimal : 3 + 3

Avec les pièces en euros, le glouton donne la meilleure réponse. Mais avec des pièces de 1, 3 et 4 pour rendre 6, il prend 4 puis doit compléter avec 1 + 1 : trois pièces, alors que 3 + 3 en demande deux. La programmation dynamique, elle, compare toutes les possibilités pour chaque montant de 1 à 6, et trouve la vraie meilleure réponse.

10.Quel outil pour quel problème ?

Pièges fréquents

Checklist avant de coder

• J'ai décrit le problème en une phrase (« je cherche… », « je dois essayer… »).
• Je sais combien de données il y aura en production, pas seulement en développement.
• J'ai repéré les boucles imbriquées et les boucles cachées.
• Je me suis demandé si la base de données peut faire le travail (WHERE, ORDER BY, index).
• Ma fonction récursive a un cas de base, et mon parcours de graphe mémorise les nœuds visités.
• J'ai testé les cas limites : liste vide, un seul élément, valeurs égales, valeurs aux bornes.
• J'ai mesuré avant d'optimiser.

Exercice : les redirections en chaîne

Un site garde une table de redirections : quand on visite une ancienne adresse, on est envoyé vers la nouvelle. Crée le fichier exemples/01/exercice.php avec ces données :

$redirects = [
    '/ancien-blog' => '/blog',
    '/blog' => '/actualites',
    '/promo' => '/soldes',
    '/soldes' => '/promo',
    '/contact-us' => '/contact',
    '/noel' => '/promo',
];

1. Écris une fonction resolve(array $redirects, string $url): string qui suit les redirections jusqu'à l'adresse finale. Vérifie que resolve($redirects, '/ancien-blog') renvoie '/actualites' et que resolve($redirects, '/contact') renvoie '/contact'.
2. Appelle resolve($redirects, '/promo'). Que se passe-t-il ? Modifie ta fonction pour qu'elle lance une LogicException quand elle détecte une boucle, y compris pour '/noel'. Indice : quelle structure de la section 2 dit en O(1) si tu es déjà passé par une adresse ?
3. Quelle est la complexité de resolve pour une chaîne de n redirections ? Et si tu appelles resolve pour chaque adresse de la table ? Bonus : utilise la mémoïsation (section 8) pour que résoudre toute la table reste en O(n).
4. Question de sécurité : ces redirections sont saisies dans un formulaire d'administration. Que se passe-t-il si quelqu'un y enregistre https://site-malveillant.example ? Quelle vérification ajouterais-tu ?

Pour exécuter ton fichier :

docker compose run --rm php php exemples/01/exercice.php

Envoie-moi ton code et tes réponses : on en fera la revue ensemble avant la fiche 2.

Conseils

1. Commence simple. Écris d'abord la version la plus lisible, puis mesure. Optimise seulement ce qui est réellement lent.
2. Dessine le problème. Sur papier, un arbre ou un graphe se voit tout de suite. Une fois dessiné, tu reconnais souvent la forme du problème.
3. Teste avec de vrais volumes. Génère 100 000 lignes avec une boucle (comme dans l'exemple de la section 1) : les problèmes de complexité n'apparaissent qu'à cette échelle.
4. Pratique par petites doses. L'Advent of Code propose chaque décembre un problème par jour, de plus en plus difficile. Les premiers jours sont abordables, et la plupart des sections de cette fiche y servent.
5. Ne te compare pas. Ces notions s'oublient quand on ne s'en sert pas, chez tout le monde. Savoir qu'elles existent et où les retrouver, c'est déjà l'essentiel.

Documentation officielle

• Les tableaux en PHP
• Trier des tableaux, et l'opérateur <=>
• array_find et array_column
• SplQueue et SplStack
• preg_match et la configuration PCRE
• levenshtein
• Le composant Cache de Symfony
• Les requêtes WITH RECURSIVE de PostgreSQL