Compter les étapes d'un algorithme

Lessons and exercises follow the school system and stay in its language.Les leçons et les exercices suivent le système scolaire et restent dans sa langue.Lektionen und Übungen folgen dem Schulsystem und bleiben in seiner Sprache.

À propos de cette leçon

Quatrième › La pensée informatique

Pour obtenir un PDF, choisis « Enregistrer au format PDF » dans la fenêtre d'impression.

Sources et crédits

Leçon originale de sedifier.

Rédigé avec l'aide d'une IA ; chaque réponse est vérifiée par notre moteur de calcul. Pas encore relu par un enseignant.

Cette leçon : CC BY-SA 4.0, © sedifier · Tous les crédits

Compter les étapes d'un algorithme

La pensée informatique. algorithme, variable, boucle

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 ?

  1. Une vingtaine
  2. Environ 500 000

L'idée clé

Compter les étapes d'un algorithme.

  • Deux boucles imbriquées de nn et mm tours : n×mn \times m passages.
  • La dichotomie sur une liste de 2k2^k éléments : au plus kk étapes (environ k+1k + 1 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 ».

30×4030 \times 40
Chaque tour de i fait 40 tours de j.
12001200 passages
Total.

À toi, guidé

À toi : liste triée de 1024=2101024 = 2^{10} éléments : nombre de divisions par deux ?

1010
210=10242^{10} = 1024.

Entraînement ★

  1. 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 ?
  2. 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 ?
  3. 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 ★★

  1. Une liste triée contient 2102^{ 10 } éléments. Combien de divisions par deux faut-il pour arriver à un seul élément ?
  2. Une liste triée contient 2202^{ 20 } éléments. Combien de divisions par deux faut-il pour arriver à un seul élément ?

Bilan

Deux questions pour vérifier.

  1. 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 ?
  2. 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 log⁡2n\log_2 n étapes.

Les moteurs de recherche choisissent des algorithmes dont le coût grandit lentement.

Sources et crédits

Leçon originale de sedifier.

Rédigé avec l'aide d'une IA ; chaque réponse est vérifiée par notre moteur de calcul. Pas encore relu par un enseignant.

Cette leçon : CC BY-SA 4.0, © sedifier · Tous les crédits