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 - insert

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 fausses réponses.

Question 1: Fonction récursive

Sélectionnez, parmi les fonctions suivantes, celle ou celles qui sont récursives.

Question 2: Taille du problème

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

Question 3: 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 insert.

Question 4: 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 insert.

Notez que la complexité temporelle de l'extraction d'une partie d'un tableau (un slice) est linéaire avec la taille de la partie extraite et que la complexité temporelle de l'addition de deux tableaux est linéaire avec la taille des deux tableaux :

#soit :
#    tab1 un tableau (list) de taille n1
#    tab2 un tableau (list) de taille n2
#    0 <= a < b <= n1
tab1[:a] #Theta(a)
tab1[a:b] #Theta(b-a)
tab1 + tab2 #Theta(n1+n2)
tab1[:a] + tab2 #Theta(a+n2)
Question 5: 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 insert?

Question 6: Complexité temporelle de la fonction

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