Lista de cursos Entrar

Informações

Autores Vincent Branders, Pierre Dupont
Prazo de entrega 08/04/2026 14:00:00
Limite de submissão No limitation

Entrar

Entrar

[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):])
Questão 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.

Questão 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.

Questão 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.

Questão 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?

Questão 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é.

Questão 6: Une solution efficace

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

Questão 7: Pourquoi est-ce si compliqué ?

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