Découvrir
On cherche un nombre entre 1 et 1 000 000 dans une liste triée. À chaque essai, on regarde le milieu et on garde la bonne moitié. Combien d'essais faut-il au plus ?
- Une vingtaine
- Environ 500 000
L'idée clé
Compter les étapes d'un algorithme.
- Deux boucles imbriquées de et tours : passages.
- La dichotomie sur une liste de éléments : au plus étapes (environ comparaisons).
Compter les étapes permet de comparer deux algorithmes.
Exemple corrigé
Une boucle « pour i de 1 à 30 » contient une boucle « pour j de 1 à 40 ».
À toi, guidé
À toi : liste triée de éléments : nombre de divisions par deux ?
Entraînement ★
- Une boucle « pour i de 1 à 36 » contient une boucle « pour j de 1 à 37 ». Combien de fois l'instruction intérieure est-elle exécutée ?
- Une boucle « pour i de 1 à 44 » contient une boucle « pour j de 1 à 43 ». Combien de fois l'instruction intérieure est-elle exécutée ?
- Une boucle « pour i de 1 à 19 » contient une boucle « pour j de 1 à 21 ». Combien de fois l'instruction intérieure est-elle exécutée ?
Entraînement ★★
- Une liste triée contient éléments. Combien de divisions par deux faut-il pour arriver à un seul élément ?
- Une liste triée contient éléments. Combien de divisions par deux faut-il pour arriver à un seul élément ?
Bilan
Deux questions pour vérifier.
- Une boucle « pour i de 1 à 36 » contient une boucle « pour j de 1 à 37 ». Combien de fois l'instruction intérieure est-elle exécutée ?
- Une boucle « pour i de 1 à 44 » contient une boucle « pour j de 1 à 43 ». Combien de fois l'instruction intérieure est-elle exécutée ?
Fiche résumé
Coût d'un algorithme
- Boucles imbriquées : on multiplie les nombres de tours.
- Dichotomie : environ étapes.
Les moteurs de recherche choisissent des algorithmes dont le coût grandit lentement.