רשימת קורסים כניסה

מידע

יוצרים Pierre Dupont
מועד הגשה 01/09/2026 16:00:00
מגבלת הגשות אין הגבלה

כניסה

כניסה

[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
שאלה 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.

שאלה 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.

שאלה 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.

שאלה 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.

שאלה 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é.