Course list Sign in

Information

Author(s) Vincent Branders, Pierre Dupont
Deadline 24/04/2024 14:00:00
Submission limit No limitation

Sign in

Sign in

[TP08] Tri par insertion - insertion_sort

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.

Question 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.

Question 2: Complexité temporelle de la fonction

Quelle est la complexité temporelle de la fonction insertion_sort ? 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é.

Question 3: Prenons du recul

Lors d'un exercice précédent, nous avons vu que la complexité temporelle du tri par insertion (tel que présenté en cours) est en \(O(n^2)\). La complexité temporelle de la méthode insertion_sort est différente, cependant.

Pouvez-vous identifier la raison de cette différence ? Selectionnez, parmi les propositions suivantes, celle ou celles qui justifient cette augmentation de la complexité temporelle de ìnsertion_sort` par rapport au tri vu en cours.