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

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

def mergesum(x, i_min, i_max):
    """
    pre: `x` un tableau d'entiers
    pre: `i_min` et `i_max`, deux entiers tels que 0 <= i_min <= i_max < len(x)
         L'appel initial à cette fonction est supposé être : mergesum(x, 0, len(x)-1)
    post: renvoie la somme des éléments de `x`
    """
    # La précondition sur i_min et i_max peut devenir non satisfaite par récursion
    if i_min > i_max:
        return 0
    middle = (i_min + i_max)//2
    return x[middle] + mergesum(x, i_min, middle-1) + mergesum(x, middle+1, i_max)
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 mergesum.

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

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

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

Spørsmål 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é.