Aller au contenu
Encyclopédie informatique Édition 2026

L'algorithmique

Partie 2 sur 3

Niveau de lecture :
Vidéo de cette partieenviron une minute et demie, avec voix et texte à l’écran

4Un exemple détaillé : chercher dans une liste

Supposons qu’il faille savoir si un nom figure dans une liste d’un million de personnes. La méthode la plus simple, la recherche séquentielle, compare le nom à chaque élément, du premier au dernier. Elle fonctionne toujours, mais dans le pire des cas, celui où le nom est absent, elle demande un million de comparaisons.

Si la liste est triée, on peut faire infiniment mieux, comme lorsqu’on cherche un mot dans un dictionnaire : on ouvre au milieu, on regarde si le mot cherché se trouve avant ou après, et l’on recommence dans la bonne moitié. C’est la recherche dichotomique (du grec dikhotomia, « division en deux »). Chaque comparaison élimine la moitié des candidats restants.

Étape 1 : le milieu vaut 37, plus petit que 63 → on garde la moitié droite 3 8 12 17 21 25 30 37 41 46 52 58 63 70 77 85 Étape 2 : le milieu vaut 58, plus petit que 63 → on garde la moitié droite 3 8 12 17 21 25 30 37 41 46 52 58 63 70 77 85 Étape 3 : le milieu vaut 70, plus grand que 63 → on garde la moitié gauche 3 8 12 17 21 25 30 37 41 46 52 58 63 70 77 85 Étape 4 : le milieu vaut 63 → trouvé, en 4 comparaisons au lieu de 13 3 8 12 17 21 25 30 37 41 46 52 58 63 70 77 85
Figure 3. Recherche de la valeur 63 dans une liste triée de seize nombres. La zone soulignée contient les candidats encore possibles ; la case en couleur est l’élément du milieu, auquel on compare la valeur cherchée.
fonction RechercheDichotomique(L, v)      // L est une liste triée
    début ← 1
    fin ← longueur(L)
    tant que début ≤ fin faire
        milieu ← début + (fin − début) div 2
        si L[milieu] = v alors renvoyer milieu
        sinon si L[milieu] < v alors début ← milieu + 1
        sinon fin ← milieu − 1
    fin tant que
    renvoyer « absent »
fin fonction

Le gain est spectaculaire. Comme on divise par deux à chaque étape, il faut au plus 20 comparaisons pour un million d’éléments (220 = 1 048 576), et 33 pour une liste de 8 milliards de noms, soit la population mondiale. Ce nombre s’appelle le logarithme en base 2 de la taille de la liste. Le prix à payer est de maintenir la liste triée.

Que faire si la valeur est absente ? L’algorithme renvoie ici une valeur spéciale, « absent ». Une autre possibilité consiste à signaler une erreur, en langage de programmation on dit « lever une exception », que le programme appelant devra traiter. Une bonne fonction laisse souvent le choix à celui qui l’appelle, par un paramètre : l’absence est-elle normale, ou anormale ?

5Mesurer l’efficacité

5.1La complexité et la notation OApprofondir

Pour comparer des algorithmes indépendamment de la vitesse des machines, on compte le nombre d’opérations élémentaires qu’ils effectuent en fonction de la taille n des données. On ne garde que l’ordre de grandeur, noté avec un O majuscule (« grand O ») : on dit que la recherche séquentielle est « en O(n) » et la recherche dichotomique « en O(log n) ». Cette mesure s’appelle la complexité en temps ; on étudie de même la complexité en mémoire. On distingue aussi le meilleur cas, le cas moyen et le pire cas : un algorithme peut être rapide en général et très lent sur certaines données.

Tableau 1. Durée approximative d’exécution selon la complexité, pour une machine qui effectue un milliard d’opérations par seconde.
ComplexitéExemplen = 10n = 1 000n = 1 million
O(1), constanteLire une case d’un tableau1 ns1 ns1 ns
O(log n), logarithmiqueRecherche dichotomique3 ns10 ns20 ns
O(n), linéaireRecherche séquentielle10 ns1 µs1 ms
O(n log n)Bons algorithmes de tri33 ns10 µs20 ms
O(n2), quadratiqueTri par sélection100 ns1 ms17 min
O(2n), exponentielleEssayer toutes les combinaisons1 µshors de portéehors de portée

Le tableau montre pourquoi le choix de l’algorithme compte souvent plus que la puissance de la machine. Quant aux algorithmes exponentiels, aucun progrès matériel ne les sauvera : pour n = 1 000, 2n opérations prendraient infiniment plus longtemps que l’âge de l’Univers.

5.2Les algorithmes de triApprofondir

Trier est l’une des opérations les plus fréquentes en informatique : elle prépare les recherches rapides, l’affichage, la détection des doublons. C’est aussi le terrain d’entraînement favori de l’algorithmique, car de nombreuses méthodes y conduisent, avec des performances très différentes.

  • Le tri par sélection cherche le plus petit élément restant et le place en tête, puis recommence avec le reste. Simple, mais toujours en O(n2).
  • Le tri par insertion procède comme un joueur de cartes qui range sa main : il prend les éléments un par un et insère chacun à sa place parmi ceux déjà triés. Il est en O(n2) dans le pire cas, mais très rapide sur une liste presque triée.
  • Le tri fusion, décrit par John von Neumann en 1945, coupe la liste en deux, trie chaque moitié par le même procédé, puis fusionne les deux moitiés triées. Il est toujours en O(n log n), mais demande une mémoire supplémentaire.
  • Le tri rapide (quicksort), inventé par le Britannique Tony Hoare en 1959, choisit un élément pivot, range à sa gauche les plus petits et à sa droite les plus grands, puis trie chaque côté. Très rapide en moyenne, il peut dégénérer en O(n2) si le pivot est mal choisi.
38 27 43 3 9 82 10 38 27 43 3 9 82 10 38 27 43 3 9 82 10 38 27 43 3 9 82 10 27 38 3 43 9 82 10 3 27 38 43 9 10 82 3 9 10 27 38 43 82 DIVISER couper en deux listes d’un seul élément : triées FUSIONNER deux listes triées liste triée
Figure 4. Le tri fusion de la liste 38, 27, 43, 3, 9, 82, 10. La moitié haute découpe, la moitié basse fusionne : pour fusionner deux listes triées, il suffit de comparer leurs premiers éléments et de prendre le plus petit, encore et encore. La liste est coupée log2 n fois, et chaque niveau de fusion demande environ n comparaisons : d’où le O(n log n).
Tableau 2. Quatre algorithmes de tri comparés. Un tri est dit stable s’il conserve l’ordre de départ des éléments égaux, et en place s’il ne demande presque pas de mémoire supplémentaire.
TriMeilleur casPire casStableEn place
Par sélectionO(n2)O(n2)nonoui
Par insertionO(n)O(n2)ouioui
FusionO(n log n)O(n log n)ouinon
RapideO(n log n)O(n2)nonoui

Trier un million de fiches avec une méthode en O(n2) prend de l’ordre d’un quart d’heure ; un tri en O(n log n) le fait en quelques centièmes de seconde. Les langages modernes combinent plusieurs méthodes : Python et Java utilisent Timsort, conçu en 2002 par Tim Peters, qui associe le tri fusion et le tri par insertion pour profiter des portions déjà triées.

5.3Les limites du calculApprofondir

Certains problèmes n’ont aucune solution algorithmique. En 1936, Alan Turing a démontré qu’il est impossible d’écrire un programme capable de dire, pour n’importe quel programme et n’importe quelles données, si ce programme finira un jour son calcul ou tournera indéfiniment. Ce résultat, appelé indécidabilité du problème de l’arrêt, a des conséquences très concrètes, y compris en sécurité (voir le coin cyber).

D’autres problèmes ont une solution, mais semblent ne pas en avoir d’efficace. Pour beaucoup d’entre eux, il est facile de vérifier une solution proposée, mais on ne connaît aucune méthode rapide pour la trouver : c’est le cas, par exemple, du remplissage optimal d’un emploi du temps soumis à de nombreuses contraintes. La question de savoir si ces problèmes, dits NP, peuvent tous être résolus rapidement est l’une des plus grandes énigmes des mathématiques : la question « P = NP ? ». Le Clay Mathematics Institute promet depuis 2000 un million de dollars à qui la résoudra ; elle reste ouverte. La cryptographie moderne repose d’ailleurs sur des problèmes que l’on croit difficiles, comme la décomposition d’un très grand nombre en facteurs premiers.

Face aux problèmes trop difficiles, on se contente souvent de méthodes approchées, les heuristiques, qui donnent rapidement une bonne solution sans garantir la meilleure. Enfin, l’apprentissage automatique a changé la donne : au lieu de décrire chaque règle, on écrit un algorithme qui ajuste lui-même ses paramètres à partir d’exemples.

Pour s’exercer

Exercice 2 : combien de comparaisons ?

Combien de comparaisons faut-il, au plus, pour trouver un élément par recherche dichotomique dans une liste triée de 1 000 éléments ? Et par recherche séquentielle ?

Voir la réponse

29 = 512 est trop petit et 210 = 1 024 suffit : 10 comparaisons au plus par dichotomie. La recherche séquentielle peut en demander 1 000.

Exercice 3 : trier par insertion

Triez la liste 5, 2, 4, 6, 1, 3 par insertion, en écrivant la liste après chaque insertion.

Voir la réponse

On part de 5. On insère 2 : 2, 5. On insère 4 : 2, 4, 5. On insère 6 : 2, 4, 5, 6 (aucun déplacement). On insère 1 : 1, 2, 4, 5, 6 (quatre déplacements). On insère 3 : 1, 2, 3, 4, 5, 6. Le nombre de déplacements dépend du désordre initial : sur une liste déjà triée, il n’y en a aucun.

Sécurité de l’information

Le coin cyber

C.1Quand la complexité devient une arme

Les attaques par complexité

Un algorithme efficace en moyenne peut avoir un « pire cas » très lent. En décembre 2011, deux chercheurs, Alexander Klink et Julian Wälde, ont montré qu’en envoyant à un serveur web des paramètres choisis pour provoquer des collisions dans ses tables de hachage, quelques requêtes suffisaient à occuper un processeur à 100 % pendant des heures. Java, PHP, Python ou Ruby étaient concernés ; la parade a consisté à rendre le calcul imprévisible pour l’attaquant et à limiter le nombre de paramètres. Le tri rapide avec un pivot prévisible présente la même faiblesse : des données choisies le font tomber dans son pire cas.

Les expressions régulières

Les expressions régulières, qui décrivent des motifs de texte, peuvent exploser en temps de calcul sur certaines chaînes. Le 2 juillet 2019, une seule règle de ce type, déployée dans le pare-feu applicatif de Cloudflare, a saturé ses processeurs dans le monde entier et rendu inaccessibles d’innombrables sites pendant une demi-heure. Ce n’était pas une attaque, mais un attaquant peut viser exactement le même effet : on parle de déni de service par expression régulière (en anglais ReDoS, Regular expression Denial of Service).

Les fuites par le temps de calcul

Un programme qui compare un mot de passe caractère par caractère et s’arrête à la première différence répond un peu plus vite quand le début est faux. En mesurant ces écarts infimes, un attaquant peut deviner le secret morceau par morceau. C’est une attaque par canal auxiliaire. Les comparaisons de secrets doivent donc s’exécuter en temps constant.

C.2Le défi des ordinateurs quantiques

En 1994, le mathématicien Peter Shor a décrit un algorithme qui, sur un ordinateur quantique suffisamment puissant, casserait les systèmes à clé publique les plus utilisés, RSA et les courbes elliptiques. Une telle machine n’existe pas encore, mais des données chiffrées aujourd’hui peuvent être interceptées et stockées pour être déchiffrées plus tard. Le NIST, l’institut américain des normes et de la technologie, a publié le 13 août 2024 trois premiers algorithmes dits post-quantiques, conçus pour résister à ces machines (normes FIPS 203, 204 et 205). L’ANSSI (Agence nationale de la sécurité des systèmes d’information) recommande une migration progressive, en combinant algorithmes classiques et post-quantiques.

C.3Les mots de passe se protègent avec des algorithmes lents

Ce chapitre vante la vitesse, mais en sécurité, la lenteur est parfois voulue. Si un site stocke vos mots de passe avec une méthode très rapide, quelqu’un qui vole la base peut en tester des milliards par seconde. Le bon réflexe, pour qui conçoit un site : employer une méthode de hachage lente et reconnue, comme Argon2 ou bcrypt, recommandée par l’OWASP, avec un sel (une valeur aléatoire propre à chaque mot de passe).