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] Mergesum 2

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

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