Kursliste Logg inn

Informasjon

Forfatter(e) Vincent Branders, Pierre Dupont
Frist 08/04/2026 14:00:00
Innleveringsgrense Ingen begrensning

Logg inn

Logg inn

[TP08] Tri par insertion - insertion_sort_h

On vous demande de calculer la complexité temporelle de l'implémentation du tri par insertion reprise dans le fichier insertion_sort.py.

Pour cela, il faudra déterminer la complexité des fonctions insertion_sort, insertion_sort_h et insert.

Note : il est toujours vivement conseillé d'essayer de répondre aux questions avant de regarder les propositions. En effet, il vous sera plus simple de repérer une réponse connue que d'essayer de l'identifier sans savoir à quoi s'attendre. De plus, votre objectif est de pouvoir répondre à une question particulière, pas d'identifier la bonne réponse parmi un ensemble de fausse réponses.

Spørsmål 1: Taille du problème

Sélectionnez, parmi les réponses proposées, celle qui définit la taille du problème de la fonction insertion_sort_h.

Spørsmål 2: Définition du cas de base de la récurrence

Sélectionnez, parmi les réponses proposées, celle qui définit le cas de base de la récurrence de la fonction insertion_sort_h.

Spørsmål 3: Définition de l'équation de récurrence dans le cas général

Sélectionnez, parmi les réponses proposées, celle qui définit le cas général de la récurrence de la fonction insertion_sort_h.

Spørsmål 4: Profondeur maximale

Quelle est la profondeur de récursion maximale, désignée généralement par \(i_{max}\), atteinte lors de l'exécution de la fonction insertion_sort_h?

Spørsmål 5: Complexité temporelle de la fonction

Quelle est la complexité temporelle de la fonction insertion_sort_h obtenue en résolvant les équations de récurrence de cette fonction ? Sélectionnez, parmi les réponses proposées, la complexité temporelle représentée par la notation \(\Omega(.), \Theta(.), O(.)\) la plus appropriée pour décrire cette complexité.

À tout hasard, sachez que \(\sum_{i = 1}^{n} i^2 = \frac{n \times (n+1) \times (2n + 1)}{6}\). Ça pourrait vous être utile. Néanmoins, si vous en avez besoin, il serait bon de prouver (par induction) ce résultat.