Lista de cursos Entrar

Informações

Autores Pierre Dupont
Prazo de entrega 01/09/2026 16:00:00
Limite de submissão No limitation

Entrar

Entrar

[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
Questão 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.

Questão 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.

Questão 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.

Questão 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.

Questão 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é.