Lista del curso Inicia sesión

Información

Autor(es) Pierre Dupont
Fecha de entrega 01/09/2026 16:00:00
Tiempo límite de envío Sin límite de envío

Inicia sesión

Inicia sesión

[Examen Blanc] Tâche 1 : Meilleur et pire cas

On souhaite trier une liste d'entiers. L'algorithme proposé est le suivant:

  • Etape 1 : créer un arbre binaire de recherche T vide
  • Etape 2 : insérer les n éléments de la liste, 1 par 1, dans T
  • Etape 3 : faire un parcours infixe de T pour récupérer la liste ordonnée
Pregunta 1: Complexité temporelle de l'étape 1

Déterminez la complexité temporelle de l'étape 1. On vous demande d'identifier la borne la plus appropriée.

Pregunta 2: Complexité temporelle de l'étape 2

Déterminez la complexité temporelle de l'étape 2. On vous demande d'identifier la borne la plus appropriée.

Attention : bien que les n éléments de T soient ajoutés un par un, on s'intéresse ici à la complexité globale, c'est-à-dire à la complexité de l'ajout des n éléments.

Pregunta 3: Complexité temporelle de l'étape 3

Déterminez la complexité temporelle de l'étape 3. On vous demande d'identifier la borne la plus appropriée.

Pregunta 4: Complexité temporelle de l'algorithme

Déterminez la complexité temporelle de l'algorithme proposé. On vous demande d'identifier la borne la plus appropriée.

Pregunta 5: Identification de pire cas

Sélectionnez, parmi les propositions suivantes, l(es) instance(s) qui correspond(ent) à un pire cas pour la complexité temporelle de l'algorithme proposé.