Rédigé avec l’aide d’une IA, relu et corrigé par l’équipe Ludicademy · mis à jour le 8 septembre 2026 · Notre méthode
- Deux algorithmes justes ne se valent pas : on compte ensuite leurs gestes
- On compte l'opération qui coûte, en fonction de la taille des données
- Couper en deux bat le parcours un par un dès que les données sont nombreuses
Le même résultat, pas le même travail
Deux algorithmes peuvent donner exactement la même réponse et ne pas se valoir. Deviner un nombre entre 1 et 100 en essayant 1, puis 2, puis 3, finit par marcher. Couper l'intervalle en deux à chaque essai marche aussi — en sept essais au pire, contre cent.
Tant qu'un algorithme est faux, seule la justesse compte. Dès qu'il est juste, une deuxième question se pose : combien de gestes fait-il ? Cette question a une réponse mesurable, et elle ne dépend ni de la machine ni de la patience de celui qui exécute.
Compter les gestes, pas les secondes
| Le problème | La méthode naïve | La méthode réfléchie | Sur 100 éléments |
|---|---|---|---|
| Deviner un nombre | Essayer 1, 2, 3… | Couper en deux à chaque coup | 100 essais contre 7 |
| Chercher un mot au dictionnaire | Lire depuis la page 1 | Ouvrir au milieu, éliminer une moitié | 1000 pages contre 10 |
| Additionner 1 + 2 + … + 100 | Ajouter cent fois | Cinquante paires valant 101 | 100 additions contre 2 opérations |
| Trouver le plus grand | Comparer chacun à tous | Garder le meilleur vu jusqu'ici | 4950 comparaisons contre 99 |
Un exemple qu'on peut dérouler à la main
La méthode du « meilleur vu jusqu'ici » mérite qu'on la suive en entier : c'est le premier algorithme dont on sent, en le déroulant, qu'il est bien meilleur que l'évidence.Trouver le plus grand de 4, 9, 2, 7. Méthode naïve : comparer chaque nombre à tous les autres, soit six comparaisons pour quatre nombres, et quatre mille neuf cent cinquante pour cent nombres. Méthode réfléchie : une variable max prend la valeur du premier, soit 4. On lit 9 : 9 est plus grand que 4, donc max devient 9. On lit 2 : non, max reste 9. On lit 7 : non, max reste 9. Trois comparaisons, une par élément restant. Sur cent nombres, quatre-vingt-dix-neuf comparaisons au lieu de quatre mille neuf cent cinquante. Le résultat est identique ; le travail ne l'est pas.

Ce qu'on compare vraiment
Pour comparer deux algorithmes, on choisit l'opération qui coûte — la comparaison, l'échange, la lecture — et on compte combien de fois elle est faite selon la taille des données. Un algorithme qui fait autant de gestes que d'éléments et un algorithme qui en fait autant que le carré du nombre d'éléments ne diffèrent presque pas sur dix données, et diffèrent d'un facteur cent sur mille.






- Deux algorithmes justes ne se valent pas : on compte ensuite leurs gestes
- On compte l'opération qui coûte, en fonction de la taille des données
- Couper en deux bat le parcours un par un dès que les données sont nombreuses
- Un petit jeu d'essai ne montre jamais la différence : elle apparaît sur les grands
Trouver le plus grand de 100 nombres avec la méthode « meilleur vu jusqu'ici » : combien de comparaisons ?
Le premier sert de point de départ, chacun des 99 autres est comparé une seule fois.
Quel critère départage deux algorithmes justes ?
La justesse une fois acquise, c'est le travail fait qui les sépare, pas leur apparence.




