Aller au contenu
Ludicademy
English
Thème Élan
ClairsSombres
S’inscrire
3e · Algorithmique

Deux algorithmes pour le même résultat : lequel choisir ?

juste ne suffit pas, il faut aussi savoir compter les gestes

≈ 4 min de lecture · palier 3e · trois questions à la fin

Rédigé avec l’aide d’une IA, relu et corrigé par l’équipe Ludicademy · mis à jour le 8 septembre 2026 · Notre méthode

En bref
  • 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èmeLa méthode naïveLa méthode réfléchieSur 100 éléments
Deviner un nombreEssayer 1, 2, 3…Couper en deux à chaque coup100 essais contre 7
Chercher un mot au dictionnaireLire depuis la page 1Ouvrir au milieu, éliminer une moitié1000 pages contre 10
Additionner 1 + 2 + … + 100Ajouter cent foisCinquante paires valant 101100 additions contre 2 opérations
Trouver le plus grandComparer chacun à tousGarder le meilleur vu jusqu'ici4950 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.

Un algorithme plus court à ÉCRIRE n'est pas un algorithme plus rapide à EXÉCUTER. « Trier puis prendre le dernier » tient en deux lignes et fait bien plus de travail que le parcours en une variable. La longueur du texte ne dit rien du nombre de gestes.

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.

SkeletMes deux versions donnent la même réponse. Elles se valent.
OscarSur combien de données les avez-vous essayées ?
SkeletCinq.
OscarEssayez sur dix mille. L'une répondra, l'autre sera encore en train de réfléchir demain.
SkeletEt sur cinq, elles étaient identiques.
OscarC'est bien le problème : la différence ne se voit que là où elle coûte.
À retenir
  • 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
Exercice

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.

Exercice

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.

Expressions à emporter

Expression Traduction
efficacitéle nombre de gestes, à résultat égal
dichotomiecouper en deux à chaque essai
meilleur vu jusqu'iciune variable qui retient le maximum

Maintenant, jouez-la

Trois questions pour voir

La règle est lue. Voyons si elle est entrée : trois questions, ici même, sans compte.

6 exercices corrigés de logique en 3e → sans compte, corrigés à chaque réponse

La règle est lue ; il reste à la faire entrer. Trois minutes suffisent.

Jouer « le pont de cordes » → Quiz Express · sans compte

Ou choisissez votre salle :

Et côté jeux de société : 🎪 Échecs → les règles d'échecs

Sur papier : 🖨️ La fiche de cette leçon

Pour réviser : 📝 La fiche de révision

Toutes les leçons 3e