Λίστα με τα μαθήματα Συνδεθείτε

Information

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

Συνδεθείτε

Συνδεθείτε

[TP08] Mergesum

Déterminez la complexité de la fonction mergesum suivante.

def mergesum(x):
    """
    pre: `x` un tableau d'entiers
    post: renvoie la somme des éléments de `x`
    """
    if len(x) == 0:
        return 0
    middle = len(x)//2
    return x[middle] + mergesum(x[:middle]) + mergesum(x[(middle+1):])
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 mergesum.

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

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

Question 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 mergesum?

Question 5: Complexité temporelle de la fonction

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

Question 6: Une solution efficace

La fonction mergesum est-elle une solution efficace au problème qu'elle résout ?

Question 7: Pourquoi est-ce si compliqué ?

Sélectionnez, parmi les propositions suivantes, celle qui justifie votre réponse à la question précédente.