Deux algorithmes pour le même résultat : lequel choisir ?
Objectif : juste ne suffit pas, il faut aussi savoir compter les gestes
L’essentiel
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.
À 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
Le tableau à connaître
| 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 |
⚠ Attention, piège
- 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.
Exemples
- Trouver le plus grand de 4, 9, 2, 7.
Le plan de la leçon
- Le même résultat, pas le même travail
- Compter les gestes, pas les secondes
- Un exemple qu'on peut dérouler à la main
- Ce qu'on compare vraiment
Je me teste
Trouver le plus grand de 100 nombres avec la méthode « meilleur vu jusqu'ici » : combien de comparaisons ?
- 100
- 99
- 4950
Quel critère départage deux algorithmes justes ?
- Le nombre d'opérations effectuées
- La longueur du texte écrit
- L'ordre alphabétique des noms
Le mot d’Oscar — Sur combien de données les avez-vous essayées ?
Réponses : 1. B · 2. A