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

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):])
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é.

Spørsmål 6: Une solution efficace

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

Spørsmål 7: Pourquoi est-ce si compliqué ?

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